Sortieralgorithmen - Selectionsort

Selectionsort erklärt (SimpleClub)

Aufgabe 1

Schaue dir das Video genau an. Vergewissere dich, dass du die Grundidee von Selectionsort erklären kannst.

Die Grundidee

Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Auswahl" oder "Selectionsort" genannt wird.

Aufgabe 2

a) Beschreibe die Grundidee des Verfahrens in Worten.

Welche Eigenschaft hat der rot unterlegte Bereich?
Welches Element wird jeweils ausgewählt und mit einem Pfeil markiert?
Was wird mit diesem Element gemacht?
Welche Eigenschaft hat der blau unterlegte Bereich?

b) Spiele den beschrieben Sortiervorgang bis zum Ende durch. Du kannst die folgende Kurznotation zur Dokumentation benutzen:

[]     [25  17  32  56  25  19   8  66  29   6  20  29]
                                             ^

[6]        [25  17  32  56  25  19   8  66  29  20  29]
                                     ^		 

[6   8]        [25  17  32  56  25  19  66  29  20  29]
                     ^		 

[6   8  17]        [25  32  56  25  19  66  29  20  29]
                                     ^

c) Hier eine Variante des oben beschriebenen Sortierverfahrens. Was wird hier anders gemacht?

d) Im Internet gibt es zahlreiche Animationen zum Sortierverfahren "Selectionsort", z.B. hier oder hier oder hier oder hier. Überprüfe mit einer Animation, ob du das Verfahren verstanden hast.

Ablaufmodellierung

Die Idee des Sortierverfahrens Sortieren durch Auswählen ist sehr einfach: Man sucht das kleinste Element im unsortierten Bereich und plaziert es in einen sortierten Bereich. Das macht man solange, wie Elemente im unsortierten Bereich sind.

Wir betrachten die Version mit zwei getrennten Bereichen (Listen):

[]     [25  17  32  56  25  19   8  66  29   6  20  29]
                                             ^

[6]        [25  17  32  56  25  19   8  66  29  20  29]
                                     ^		 

[6   8]        [25  17  32  56  25  19  66  29  20  29]
                     ^		 

[6   8  17]        [25  32  56  25  19  66  29  20  29]
                                     ^

...

Informell lässt sich dieser Ablauf so beschreiben:

ALGORITHMUS selectionsort
Übergabe: Liste L
unsortierter Bereich ist die gesamte Liste L
der sortierte Bereich ist zunächst leer
SOLANGE der unsortierte Bereich noch Elemente hat:
    suche das kleinste Element im unsortierten Bereich
	entferne es im unsortierten Bereich
	füge es im sortierten Bereich an letzter Stelle an
    Rückgabe: sortierter Bereich

Aufgabe 3

Implementiere den Algorithmus selectionSort (in einer der betrachteten Varianten) und teste das entwickelte Programm mit Processing.

Vorlage

int[] sortiere(int[] liste) {
  return liste; // Hier kommt eure Implementation hin
}
 
void setup() {
  int[] liste = { 25,  17,  32,  56,  25,  19,   8,  66,  29,   6,  20,  29 };
 
  println("unsortiert:");
  printArray(liste);
 
  liste = sortiere(liste);
 
  println("sortiert:");
  printArray(liste);
}

Lösung

void printArrayWithMarker(int[] liste, int bereichsGrenze, int kleinstes) {
  print("[");
  for (int i = 0; i < bereichsGrenze; i++) {
    print(liste[i]);
 
    if (i < bereichsGrenze - 1) print(",");
  }
  print("] [");
 
  for (int i = bereichsGrenze; i < liste.length; i++) {
    if (i == kleinstes) print('#');
 
    print(liste[i]);
 
    if (i < liste.length - 1) print(",");
  }
 
  println("]");
}
 
int[] sortiere(int[] liste) {
  for (int bereichsGrenze = 0; bereichsGrenze < liste.length; bereichsGrenze++) {
    // Sortierter Bereich wird immer größer,
    // Unsortierter Bereich kleiner
    int kleinstes = bereichsGrenze;
 
    // Kleinstes Element im unsortierten Bereich suchen
    for (int i = bereichsGrenze; i < liste.length; i++) {
      if (liste[i] < liste[kleinstes]) {
        kleinstes = i;
      }
    }
 
    printArrayWithMarker(liste, bereichsGrenze, kleinstes);
 
    // Kleinstes Element an sortierten Bereich anhängen,
    // mit "unsortiertem Element" tauschen
    int tmp = liste[bereichsGrenze];
    liste[bereichsGrenze] = liste[kleinstes];
    liste[kleinstes] = tmp;
  }
 
  return liste;
}
 
void setup() {
  int[] liste = { 25,  17,  32,  56,  25,  19,   8,  66,  29,   6,  20,  29 };
 
  println("unsortiert:");
  printArray(liste);
 
  println("sortieren:");
  liste = sortiere(liste);
 
  println("sortiert:");
  printArray(liste);
}