Uitwerking Opgaven Programmeermethoden, najaar 2020 - opgaven 54/57 Opgave 54 a. void bergop (int A[ ], int i, int j) { int temp = A[i], k = i + 1; while ( ( k < j ) && ( A[k] < temp ) ) { A[k-1] = A[k]; k++; } // while A[k-1] = temp; } // bergop b. void sorteer (int A[ ], int n) { // die int n is er wel netjes bij int i; for ( i = n - 2; i >= 0; i-- ) bergop (A,i,n); } // sorteer c. 1 vergelijking om 2 op te bergen, 2 voor het getal 3, 3 voor 4, ..., n-2 voor n-1, en n-1 voor n. Samen: 1+2+3+...+n-1 = n(n-1)/2. d. Slechtste geval: evenveel. Beste geval: 1,2,3,...,n: deze methode doet er n-1, de 'gewone' bubblesort doet er altijd n(n-1)/2: veel slechter dus. e. Gewoon de code van b, of in een keer (en dan andersom er doorheen lopend): void invoegsorteer (int A[ ], int n) { // sorteer A met invoegsorteer (insertion sort) int i, // i-de element straks steeds invoegen j, // om reeds gesorteerde stuk af te lopen temp; // om tijdelijk tussen te voegen getal te bevatten for ( i = 1; i < n; i++ ) { // voeg A[i] in op juiste plaats temp = A[i]; j = i - 1; while ( ( j >= 0 ) && ( A[j] > temp ) ) { A[j+1] = A[j]; j--; } // while A[j+1] = temp; } // for } // invoegsorteer Opgave 55 a. Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 waarde 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 stap 1 * # $ ! ... * # $ ! ... (vergelijk de aangegeven elementen: *, #, $ , !, ..., net zolang tot ze onderling gesorteerd zijn); we krijgen dan: waarde 503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703 stap 2 * # $ ! * # $ ! * # $ ! * # $ ! (sorteer de elementen bij * onderling, die bij #, ...); dit was stapgrootte 4: de rij is nu 4-gesorteerd: waarde 503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703 * * * * * * * * sorteer nu de elementen op afstand 2 (de *-en) en de overige elementen: waarde 154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703 * * * * * * * * * * * * * * * * resteert de laatste ronde, het 1-sorteren: waarde 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 b. Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 waarde 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 * * * sorteren over afstand 7: waarde 275 087 426 061 509 170 677 503 653 512 154 908 612 897 765 703 * * * * * * sorteren over afstand 3: waarde 061 087 170 275 154 426 512 503 653 612 509 765 677 897 908 703 * * * * * * * * * * * * * * * * sorteren over afstand 1: waarde 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 c. Zie dictaat, Hoofdstuk 6.7.6. d. Dezelfde rij sorteren met invoegsorteer. De $ geeft telkens de grens aan tussen het gesorteerde stuk en het ongesorteerde stuk van het array. Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 waarde 503$087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 waarde 087 503$512 061 908 170 897 275 653 426 154 509 612 677 765 703 waarde 087 503 512$061 908 170 897 275 653 426 154 509 612 677 765 703 waarde 061 087 503 512$908 170 897 275 653 426 154 509 612 677 765 703 ........ waarde 061 087 154 170 275 426 503 509 512 653 897 908$612 677 765 703 waarde 061 087 154 170 275 426 503 509 512 612 653 897 908$677 765 703 waarde 061 087 154 170 275 426 503 509 512 612 653 677 897 908$765 703 waarde 061 087 154 170 275 426 503 509 512 612 653 677 765 897 908$703 waarde 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908$ Opgave 56 a. Kopieer 3 opzij; zet de getallen kleiner dan 3 vooraan, groter dan 3 achteraan; we krijgen: 2 1 --3-- 4 9 5 7 De getallen groter dan 3 komen andersom in het "nieuwe" array terecht als we ze -van linksaf komend- van rechtsaf opbergen, en soms wil je dat niet. Dit hangt af van de wijze waarop het splitsen geprogrammeerd is. Daarna worden recursief het beginstuk 2 1 en het eindstuk 4 9 5 7 gesorteerd. Etcetera. b. Dat gaat niet zo goed. Het kleinste getal komt vooraan, en alle andere getallen in het eindstuk erachter, waarschijnlijk omgekeerd als bij onderdeel a. Dan komt het grootste getal achteraan, en de rest in het middengedeelte. Etcetera, zie onderdeel c. c. Eerst komt 4 achteraan; 3 2 1 wordt het resterende te sorteren array. Weer komt de grootste achteraan; 2 1 blijft over. Dan komt 2 achteraan en is het array gesorteerd. Niet zo snel dus. Opgave 57 a. p is een pointer naar (oftewel het adres van) een int *p is datgene waar p het adres van is: een int dus, en wel het geheugenvakje met adres p &p is het adres van p zelf q is ook een pointer naar een int s is zelf een int! &getal is het adres van de int getal (dit mag dus in een variabele van type int* gestopt worden, bijvoorbeeld: p = &getal;) A is een een array met 10 int's, maar eigenlijk is A het adres van het 0-de array-element: A == &A[0] dus A[3] is het vierde array-element van het array A, een int dus; we spreken toch vaak van het derde array-element: denk eraan dat arrays beginnen met het 0-de array-element A[10] zit niet in het array, maar zonder verdere waarschuwing wordt de eerste int na het array hiervoor gepakt! b. A[3] oftewel *(A + 3) (slik) of ook *&A[3] c. Nee, want int* p, q; is hetzelfde als int* p; int q; , dus q is een int! d. A[9] is het negende (tiende?) en laatste array-element; *A[9] is *(A[9]), en betekent niet veel - hopelijk een foutmelding; &A[9] is het adres van het negende (tiende?) array-element; (*A)[9]: *A is A[0], een int dus ... maar A[0][9] is niks; *(A[9]): ook al niks zinnigs. e. Dit levert hopelijk een foutmelding op: p is een pointer, getal een int. f. Mits q ergens naar wijst, wordt hier 7 in gestopt. g. Zie e. (p = new int maakt nog wel een nieuwe int aan, en zet diens adres in p)