Quicksort

B

Burgess

0
Erstmal Hallo alle zusammen.

Ziemliches Anfängerproblem gerade bei mir....
Ich habe mich schon vor einiger Zeit mal mit Quicksort beschäftigt. Dabei hatte ich eigentlich auch angenommen das Ganze verstanden zu haben, allerdings stoße ich gerade wieder darauf und bin etwas verwirrt.

Grundlegend steht auf dieser Seite (Hier), dem zugehörigen Wikipedia Artikel und auch in einem Buch das ich besitze folgendes:

Zunächst wird die zu sortierende Liste in zwei Teillisten ("linke" und "rechte" Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste.
Zum Vergrößern anklicken....

Als ich mich das Erste mal mit Quicksort befasst habe war dort immer das mittlere Element im Array als Pivot gewählt worden. Wobei mir grundsätzlich bekannt ist/war, dass theoretisch jedes Element genommen werden kann.

Jetzt bin ich aber im Internet schon öfter auf Implementierungen von Quicksort gestoßen, die zwar funktionieren, diese Aussage allerdings nicht 100% umsetzen.

Beispiel ist hier ein Perl Algorithmus, der auch auf der oben genannten Seite unter den Implementierungen zu finden ist. (Hier)

Code: 
sub quicksort {
    my ( $aref , $links , $rechts , $compare ) = @_;

    my ($l,$r,$pivot) = (
        $links,$rechts,
        $aref->[ int +($links+$rechts) / 2 ]
    );

    while( $l <= $r ){

        $l++ while $compare->( $aref->[$l], $pivot      ) == -1;
        $r-- while $compare->( $pivot     , $aref->[$r] ) == -1;

        if ( $l <= $r ) {

              @{$aref}[$l,$r] = @{$aref}[$r,$l];
              $l++;$r--;

        }
    }

    quicksort( $aref, $links, $r,  $compare) if $links < $r;
    quicksort( $aref, $l, $rechts, $compare) if $l < $rechts;
}

Ich hätte auch noch andere Implementierung die wie diese arbeiten.
Wählt man als Eingabedaten mal diese Zahlen:
my @ar = qw/26 55 24 93 16 27 89 67 49 90 56/;
und lässt sich vor dem ersten Rekursiven Aufruf das Array ausgeben, stehen die Elemente nicht wie es sein sollte rechts und links vom Pivot (je nach Größe).
Die Ausgabe wird sein: 26 27 24 16 93 55 89 67 49 90 56 bei Pivot 27

So wie obiger Ablauf war auch der erste Quicksort, mit dem ich Kontakt hatte. Deswegen bin ich jetzt relativ verwundert, dass die Standardimplementierung und Logik wohl anders arbeitet.

Was genau hat es damit auf sich?

Danke schonmal.
 
Hallo,
wenn 27 wirklich das Pivot Element ist, dann wäre
26 27 24 16 93 55 89 67 49 90 56

eindeutig falsch sortiert.
 
Also bevor das erste mal die Rekursion aufgerufen wird hat das Array diese Form. Ganz am Ende ist logischerweise alles passend sortiert.
 
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
 
Original von Burgess


Ich hätte auch noch andere Implementierung die wie diese arbeiten.
Wählt man als Eingabedaten mal diese Zahlen:
my @ar = qw/26 55 24 93 16 27 89 67 49 90 56/;
und lässt sich vor dem ersten Rekursiven Aufruf das Array ausgeben, stehen die Elemente nicht wie es sein sollte rechts und links vom Pivot (je nach Größe).
Die Ausgabe wird sein: 26 27 24 16 93 55 89 67 49 90 56 bei Pivot 27
Zum Vergrößern anklicken....

Hi,

Deine Ausgabe ist afaik korrekt.
Wie du schon beschrieben hast, sind alle Elemente kleiner (bzw gleich, je nach Anordnung der Elemente) dem Pivotelement in der linke Teilliste und Elemente welche größer sind, befinden sich in der rechten Teilliste. Diese Ausage trifft bei dem Perl bzw VB Code zu.

Wobei man natürlich auch die rechte Teilmenge mit Elementen >= Pivotelement und die linke mit Elementen < Pivotelement füllen kann.

Schritt für Schritt:
Code: 
array = 26 55 24 93 16 27 89 67 49 90 56;             => pivotelement= 27
linker Teil = 26 27 24 16                      
Also alle Elmente sind <= den Pivotelement


array = 26 27 24 16                                                 => pivotelement = 27
linker Teil = 26 24 16
In diesem Fall sind alle Elemente < Pivotelement im linken Teil.


array = 26 24 16                                                     => pivotelement = 16
linker Teil = 16
=> Sortiert
usw...

Je nachdem wie die Elemente im Array vorliegen, ist der linke Teil < oder <= Pivotelement.

Außerdem wird vorallem bei großen Arrays das Pivotelement errechnet zb.:
(array[0]+array[arraylänge/2]+array[arraylänge-1])/3.
 
Verwirrt hat mich, dass bei diesen Implementierung das Pivot selbst mit gemischt wird und nicht genau die Trennung zwischen den Teilmengen bildet.
Dass die Teilmengen immer genau passen hatte ich auch bemerkt. (Immerhin klappt ja alles).

Mich würde interessieren ob diese Vorgehensweiße irgendwie eine Optimierung von Quicksort ist? Oder schneller ist?
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben