Ja die Beschreibung ist gut und spiegelt auch das was ich in einem Buch und unter oben genannten Link gelesen habe.
Allerdings erst jetzt. Vor ca. einem Jahr als ich das erste mal Kontakt zu Quicksort hatte, hatte ich nur eine Visual Basic Implementierung, die so vorging wie das Perl Skript oben.
Ich bin jetzt eben extrem darüber verwundert, dass diese Implementierungen die Grundlogik von Quicksort nicht unbedingt befolgen, aber trotzdem zu einem passenden Ergebnis kommen. (Und eben auch als Quicksort verkauft werden^^)
Ist die Implementierung, bei der das Pivot nicht genau genau zwischen den größeren und kleineren Elementen steht, denn eine Optimierung des Algorithmus, oder was hat es mit diesem Unterschied auf sich?
Ich poste auch mal den
VB Code (sorry.. ist eine etwas unnötig lange Version):
Code:
Private Function QSort(feld, Optional ByVal l As Integer = 0, Optional ByVal r2 As Integer = 0)
Dim r, x, i, j As Integer
Dim auslager
If r2 = 0 Then
r = UBound(feld)
Else
r = r2
End If
i = l
j = r
x = feld((j + i) / 2)
Do
Do
If feld(i) < x Then
i = i + 1
Else
Exit Do
End If
Loop
Do
If x < feld(j) Then
j = j - 1
Else
Exit Do
End If
Loop
If i <= j Then
auslager = feld(i)
feld(i) = feld(j)
feld(j) = auslager
i = i + 1
j = j - 1
End If
Loop Until i > j
If l < j Then QSort feld, l, j
If i < r Then QSort feld, i, r
End Function