• Increase font size
  • Default font size
  • Decrease font size

Quicksort

E-Mail Drucken PDF




        





Sir Tony (C.A.R.) Hoare

Im Gegensatz zu den einfachen Sortierverfahren versucht Quicksort nicht eine gesamte Liste zu sortieren, sondern viele kleine. Eine vollständige Traversierung ist so unter Umständen gar nicht nötig. Man hat das Problem auf kleinere Probleme zurückgeführt. Die Strategie für diese Vorgehensweise findet nicht nur in der Sortierung Verwendung. In der Fachsprache nennt man dies divide and conquer bzw. teile und herrsche. Der Code für den Quicksort gestaltet sich wie folgt.

        01  def quicksort (feld):
02 _qsort (feld, 0, len(feld) -1)
03 return feld
04
05 def _qsort (feld):
06
07 L = Links
08 R = Rechts
09 Links < Rechts :
10
11 pivot = feld [(Links+Rechts)/2]
12 feld [L] < pivot : L = L + 1
13 feld [L] > pivot : R = R - 1
14 if L <= R:
15
16 feld [R], feld [L] = feld [L], feld [R]
17 L = L + 1
18 R = R - 1
19
20 _qsort (feld, Links, R)
21 _qsort (feld, L, Rechts)



[Source]

 


Der Quicksortalgorithmus läßt sich auch auf andere Weise implementieren. Es besteht die Möglichkeit, die Methoden filter oder lamda zu verwenden. Allerdings wäre hier die Verwendung einer funktionalen Sprache geeigneter.
Aktualisiert ( Mittwoch, 19. Januar 2011 um 20:23 Uhr )  

(c) g-ymnasium.de 2006 - 2013 + Administrator