Einfache Sortierverfahren

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

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

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

07      return liste

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.