Index

Erstellen einfacher Programme

2. Algorithmen (12)


Sortieralgorithmen
- 5. Quicksort

Bei diesem Verfahren wird nach dem Prinzip "teile und herrsche" vorgegangen, was in der Informatik einer wichtigen Arbeitsweise entspricht. Es bedeutet, teile das Problem in kleinere Teilprobleme, evtl. diese weiter, bis du beherrschbare (genügend einfache) Probleme erhälst.

Das Verfahren Quicksort, also schnelles Sortieren, stammt von C. A. R. Hoare.

Unsortierte Liste:

90 20 12 72 2 51 47 80

Zunächst wird die Liste nach folgender Art in zwei Teile geteilt:

  1. Man greift sich aus der Mitte der Liste ein Vergleichselement. Z.B.: 72
  2. Links und rechts wird auf die Randelemente je ein Zeiger gesetzt. (l bzw r)
90 20 12 72 2 51 47 80
l             r
  1. Der Zeiger l wird solange nach rechts verschoben, bis das darüberstehende Datenelement größer oder gleich dem Vergleichselement ist. Im Beispiel ist das schon der Fall.
  2. Der Zeiger r wird solange nach links verschoben, bis das darüberstehende Datenelement kleiner oder gleich dem Vergleichselement ist.
90 20 12 72 2 51 47 80
l           r <
  1. Die angezeigten Elemente werden ausgetauscht und die Zeiger eine Position weiter gesetzt.
47 20 12 72 2 51 90 80
  l       r    
  1. Die Schritte 3 bis 5 werden wiederholt, bis die Zeiger sich überlappen, also der linke rechts vom rechten Zeiger steht.
47 20 12 72 2 51 90 80
  > > l   r    
47 20 12 51 2 72 90 80
        l r      
47 20 12 51 2 72 90 80
        r   > l    

Es ist nun eine Situation entstanden, dass links vom ausgewählten Element nur noch Elemente kleiner oder gleich diesem Vergleichselement, rechts davon nur noch solche größer oder gleich dem Vergleichselement stehen.
Man kann daher nun die Liste zwischen den Zeigern trennen. Beim späteren Zusammensetzen ist ja gewährleistet, dass von links nur kleinere oder höchstens gleich dem kleinsten Element der rechten Teilliste, von rechts nur größere oder mindestens gleich dem größten Element der linken Teilliste dazukommen.

Danach fährt man mit den Teillisten wieder nach den Punkten 1 bis 6 fort.
Enthält eine Teilliste nur noch zwei Elemente, werden diese einfach verglichen und gegebenenfalls ausgestauscht, so dass das größere Element nach rechts kommt.
Enthält eine Teilliste nur ein Element, so ist das Verfahren ebenfalls beendet.

47 20 12 51 2   72 90 80
l       r   l   r
2 20 12 51 47   72 90 80
  l   r     > l r
2 20 12 51 47   72 80 90
  l r <       r l
2 12 20 51 47   72 80   90
  r l       o k   o k
2 12   20 51 47
o k   l   r
20 51 47
> l r
20 47 51
  r l
20 47   51
o k o k

Setzt man nun die Teillisten von links nach rechts zusammen, so erhält man die sortierte Liste.

Sortierte Liste:

2 12 20 47 51 72 80 90

Das Verfahren scheint zunächst nicht sehr effektiv. Bei kleinen Datenmengen mag es gegenüber anderen Verfahren sogar im Nachteil sein. Betrachtet man die Vertauschungen, so ergaben sich im Beispiel gerade mal 6. Vergleiche waren es 24.
Durch das Teilen reduziert sich der Aufwand, was sich bei großen Datenmengen deutlich bemerkbar macht. Der Aufwand ist in der Größenordnung ld n (O(ld n)). Gegenüber dem quadratischen Aufwand ist es also bei größerer Datenmenge auf jeden Fall stark im Vorteil.

[Struktogramm] zu diesem Sortieralgorithmus.

[Index] [Zurück/Sortieren 4]


Autor: Jürgen Dehmer
Letzte Änderung: 28. April 2001