Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Sortieren durch Einfügen 1)
 

 
 



Voraussetzung
 
Sortieren durch Einfügen ist eines der einfachen Sortierverfahren.

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


Wenn A[0] bis A[i-1] bereits sortiert sind,
füge A[i] an der richtigen Stelle in diese sortierte Teilfolge ein.
Verschiebe dazu die Datensätze mit größerem Schlüssel um eins nach rechts.

Prinzip: Dynamisch, denn es werden "optimale Teillösungen" aufgebaut (sortierte Teilfolgen), die aber zunächst noch nicht einem Teilabschnitt der gesuchten Folge entsprechen.
 



Kartenspieler sortieren nach dieser Methode
 
Um die Wirkungsweise zu verstehen, solltest du folgende Übung durchführen.

   Sortiere ein Kartenspiel, indem du die Karten der Reihe nach verdeckt aufnimmst.
Du wirst spontan nach der Idee von "Sortieren durch Einfügen" vorgehen.

(Du hast gerade keine  Karten da?)

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

Der Algorithmus


für i=1 bis n-1:
    wenn A[i].Schluessel < A[i-1].Schluessel dann:
    (sonst ist A[i] bereits an der richtigen Stelle )
       speichere A[i] in einer Hilfsvariablen v
       j = i
       (suche nach dem richtigen Platz)
       solange j>0 und A[j-1].Schluessel > v.Schluessel:
             verschiebe A[j-1] um einen Platz nach rechts
             j = j-1
        (jetzt ist erstmalig A[j-1].Schlüssel <= v.Schlüssel)
        speichere die Hilfsvariable v in A[j] (freier Platz)
    (A[0] ... A[i] ist sortiert)
 
Seite 3/17