Selectionsort
Insertsort
Bubblesort
Script zu Sortierverfahren
Um die ungeordnete Listen zu ordnen, verwendet man Sortierverfahren. Sortierungen stellen dann eine wesentliche Voraussetzung für Suchverfahren dar. Um zu einer sortierten Liste zu gelangen, gibt es verschiedene Vorgehensweisen.
Das bekannteste Verfahren ist wahrscheinlich die Selektion (Selectionsort), Man nimmt aus einer Liste das kleinste Element, streicht es aus der Liste, und nimmt als nächstes wieder das kleinste Element aus der jetzt bestehenden Liste, solange, bis die Liste leer ist.Die Sortierung eines Kartenspiels erfolgt dagegen anders. Zuerst hat man keine Karte, dann die erste die logischerweise sortiert ist, die zweite Karte muss schon eingefügt werden, die dritte ebenso .... So sollte man zwar nicht Skat spielen, aber Karten sortiert man in der Regel auf diese Weise. Man fügt die Karten nach einem Relationsmuster ein, (Insertsort). Beide Verfahren erinnern stark an rekursive Algorithmen. Ein weiteres Verfahren ist (Bubblesort), das wahrscheinlich bekannteste einfache Sortierverfahren. Es gibt aber kaum eine Entsprechung in der Realität, zudem ist dieses Verfahren in Bezug auf seine Effizienz mit Abstand das schlechteste. Alle Verfahren lassen sich sowohl rekursiv, als auch iterativ programmieren.
Selectionsort - Sortieren durch Auswählen
Rekursives Selectionsort
Um diese Implementierung durchzuführen, sind Listenfunktionen notwendig.
01 def selectionsort (liste):
02 if liste == [] : return []
03 else :
04 return cons (min (liste), selectionsort (delete(min(liste),liste))),
|
Iterative Variante
01 def selectionsort (liste):
02 for i in range (0, len(liste) - 1):
03 k = i
04 # suche kleinsten Wert aus dem Rest der Liste
05 for j in range (i+1, len (liste)):
06 if liste [j] <= liste [k] : k = j
07
08 speicher = liste [k]
09 liste [k] = liste
10 liste = speicher
11
12 return liste
|
Insertsort - Sortieren durch direktes Einfügen
Rekursives Insertsort
Die Logik von Insertsort entspricht real wie oben beschrieben der Vorgehensweise beim Kartenlegen. Auch Insertsort zählt zu den einfachen Sortierverfahren, arbeitet aber, wenn auch linear, relativ gut. Eine Verbesserung dieses Algorithmus stellt Shellsort dar. Die ebenfalls rekursiv implementierte Methode ins dient dem Einfügen eines Elementes in eine geordnete Liste.
01 def ins (elem, liste):
02 if liste == [] : return [elem]
03 elif hd(liste) < elem : return cons(hd(liste), ins (elem, tl(liste)))
04 else : return cons (elem, liste) 06 def insertsort (liste):
07 if liste == [] : return []
08 else : return ins (hd(liste), insertsort (tl(liste))),
|
Iterative Variante
01 def insertsort (liste):
02 for aktuell in range (1, len(liste)):
03 speicher = liste [aktuell]
04 zeiger = aktuell
05 while (zeiger > 0) and (speicher < liste [zeiger - 1]) :
06 liste [zeiger] = liste [zeiger -1]
07 zeiger = zeiger -1
08 liste [zeiger] = speicher
09
10 return liste
|
Bubblesort - Sortieren durch direktes Austauschen
Bubblesort zählt wie oben angedeutet zu den schlechtesten Sortierverfahren, die es gibt. Trotzdem die Methode vor allem imperativ leicht zu implementieren ist, wird sie kaum verwendet. Selectionsort und Insertsort sind aufgrund ihrer Nähe zur Realität für die Lehre vorzuziehen. Allerdings kann Bubblesort aufgrund seiner Laufzeit deutlich machen, welche Eigenschaften andere Verfahren, im Besonderen höhere Sortierverfahren haben.Rekursives Bubblesort
Die rekursive Variante stützt sich hier auf die Methode bubble ab, welche benachbarte Elemente im Falle einer inversen Relation tauscht. Dadurch gelangt das in diesem Durchlauf größte Element nach hinten. Im weiteren muß also "nur noch" die Liste ohne das letzte Element durchsucht werden.Dieser Algorithmus macht gut die Nachteile einfacher Sortierverfahren deutlich, welche vor allem in der Laufzeit und der Menge der notwendigen Vergleiche zu suchen sind.
01 def bubble (liste):
02 if liste == [] : return []
03 elif len(liste) == 1 : return liste
04 elif hd(liste) > hd(tl(liste)) :
05 return cons(hd(tl(liste)), bubble (cons(hd(liste), (tl(tl(liste))))))
06 elif hd(liste) < hd(tl(liste)) :
07 return cons(hd(liste), bubble (cons(hd(tl(liste)), (tl(tl(liste)))))) 08 def bsort (liste):
09 if liste == [] : return []
10 else : return concat (bsort (init(bubble(liste))),[last (bubble(liste))])
|
Iteratives Bubblesort
01 def bubble (liste):
02 for j in range (0,len(liste)):
03 for zeiger in range (0, len(liste)-2):
04 if liste [zeiger] > liste [zeiger+1] :
05 liste [zeiger+1], liste [zeiger] = liste [zeiger], liste [zeiger+1] # swap
06
07 return liste
|
Sortierverfahren Laufzeit Selectionsort O[n²] Insertsort O[n²] Bubblesort O[n²] |