Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Sortieren durch Auswahl 1)
 

 
 
greedy = gierig



Voraussetzung
 
Als "Greedy" bezeichnet man Methoden, die direkt auf das Ziel zusteuern. Wie im richtigen Leben muss das aber nicht unbedingt die beste Strategie sein.

Gegeben ist ein Feld A mit n Positionen, also A[0] ... A[n-1], in welches die zu sortierenden Datensätze eingetragen sind.
Mittels A[i].Schluessel können wir auf den Schlüssel des i-ten Datensatzes zugreifen.
 
Die Idee des Verfahrens
 

Die Idee


In Schritt i wird in Position i der richtige (also der i-kleinste) Datensatz angebracht.
Dazu muss der dort bisher vorhandene Datensatz mit dem kleinsten aus A[i],...,A[n-1] vertauscht werden.

Prinzip: "Greedy", denn in jedem Schritt wird die richtige Entscheidung getroffen: An Position i kommt der Datensatz, der dort auch in der Lösung steht.
 



Praktische Übung: Kleingeld sortieren
 
Um die Wirkungsweise zu verstehen, solltest du folgende Übung durchführen.
   Schütte alle Münzen deines Portmonnaies auf den Tisch und sortiere nach Wert.
Du wirst spontan nach der Idee von "Sortieren durch Auswahl" vorgehen.

(Du hast gerade keine  Münzen da?)


Diese Idee ist in folgendem Algorithmus präzisiert.
 
Der Algorithmus
 

Der Algorithmus


für i=0 bis n-2:
    (suche kleinsten Schlüssel s und seine
     Position p in A[i] ... A[n-1])

    initialisiere: s = A[i].Schluessel, p = i
    für j=i+1 bis n-1:
       wenn A[j].Schluessel < s dann:
             setze s = A[j].Schluessel, p = j
        (an Pos. p ist der kleinste Schlüssel in A[i] ... A[j])
    (an Pos. p ist der kleinste Schlüssel in A[i] ... A[n-1])
    vertausche A[i] und A[p]
    (A[0] ... A[i] ist sortiert, die Schlüssel der restlichen
    Datensätze sind größer oder gleich A[i].Schlüssel)
 
Seite 6/17