Einfache und höhere Sortierverfahren

[Back]    [Selectionsort]    [Insertsort]    [Bubblesort]    [Quicksort]   

Um 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 Vorgehensweise.
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 imperativ 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             : return cons (min (liste), selectionsort (delete(min(liste),liste)))

Imperative 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 [i]
10          liste [i]  = speicher
11 
12      return liste

[TOP]

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)))

Imperative 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

[TOP]

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)) : return cons(hd(tl(liste)), bubble (cons(hd(liste), (tl(tl(liste))))))
05      elif hd(liste) < hd(tl(liste)) : return cons(hd(liste), bubble (cons(hd(tl(liste)), (tl(tl(liste))))))
    
06   def bsort (liste): 
07      if   liste == [] : return []
08      else             : return concat (bsort (init(bubble(liste))),[last (bubble(liste))])

Imperatives Bubblesort

01   def bubble (liste): 
02      for j in range (0,len(liste)):
03        for i in range (0, len(liste)- 1):    
04              if liste [i] > liste [i+1] :
05                 liste [i+1], liste [i] = liste [i], liste [i+1] # swap
06  
07      return liste

[TOP]

Die oben beschriebenen Sortierverfahren sortieren die Liste oder das Feld am Platz. Die Sortierung erfolgt also auf der Ausgangsliste. Im schlimmsten Fall (worst case) müssen alle Listen n x n mal durchlaufen werden. 

  Sortierverfahren        Laufzeit 
     
  Selectionsort           O(n²)  
  Insertsort              O(n²) 
  Bubblesort              O(n²)

Trotzdem die Laufzeit dieser Methoden quadratisch ist, können einfache Verfahren mitunter effizienter als höhere Verfahren sein. Zwar spielen für die Komplexität die Anzahl der Vergleiche und Verschiebungen (Compare and Move) eine entscheidende Rolle, aber Sortierverfahren der Ordnung O(n²) können vor allem für kleine Datenmengen ausreichend sein. Allerdings ist dieses Vorgehen für große Bestände an Daten nicht geeignet.

[Listenmodul ]