Quicksort

[Back]   

Quicksort



 
        

        

        

        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        if Links < Rechts :
	10          pivot = feld [(Links+Rechts)/2]
        11
        12          while L <= R :
        13             while feld [L] < pivot : L = L + 1
        14             while feld [R] > pivot : R = R - 1
        15             if L <= R:
	16
        17               feld [R], feld [L] = feld [L], feld [R]
        17               L = L + 1
        18               R = R - 1
	20
        21          _qsort (feld, Links,  R)
        22          _qsort (feld, L, Rechts)
	


        [Source]

[TOP]

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.



  [Protected]