TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 7
Zur Navigation springen
Zur Suche springen
Wie müssten Sie den Algorithmus Selection Sort ändern, damit eine beliebige Eingabefolge absteigend sortiert wird? Geben Sie den Pseudocode für Ihren veränderten Algorithmus an und führen Sie ihn auf der folgenden Eingabe aus: <3,6,8,2,0,1,13,6> Stellen Sie die Daten nach jeder Iteration (äußere für-Schleife) dar. Markieren Sie jeweils die Datenelemente, deren Position sich verändert haben.
Algorithmus[Bearbeiten | Quelltext bearbeiten]
rev_SelectionSort(var A) //Eingabe: unsortierte Folge A //Ausgabe: absteigend sortierte Folge in Feld A //Variablen: maxpos, i, j 1: für j = 1,..,n { 2: maxpos = j; 3: für i = j+1,..n { 4: falls A[i] > A[maxpos] dann { 5: maxpos = i; 6: } 7: } 8: falls maxpos > j dann { 9: vertausche A[maxpos] mit A[j]; 10: } 11: }
Beispielfolge[Bearbeiten | Quelltext bearbeiten]
3,6,8,2,0,1,13,6 | j=1, maxpos=7
13,6,8,2,0,1,3,6 | j=2, maxpos=3
13,8,6,2,0,1,3,6 | j=3, maxpos=3
13,8,6,2,0,1,3,6 | j=4, maxpos=8
13,8,6,6,0,1,3,2 | j=5, maxpos=7
13,8,6,6,3,1,0,2 | j=6, maxpos=8
13,8,6,6,3,2,0,1 | j=7, maxpos=8
13,8,6,6,3,2,1,0 | fertig