TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 7

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

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

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