Tutorial: Sortier-Algorithmen I+II

[Daniel]

Bitte beachten: Dieses Tutorial muss überarbeitet werden, dazu fehlt im Moment aber einfach die Zeit.sorry


Sortier-Algorithmen

Eines der grundlegenden Probleme der Informatik: Das Sortieren einer Menge an Daten. Es gibt viele verschiedene Verfahren, die sich mehr oder weniger gut für den Einsatz in einem Programm eignen.

Man kann Sortierverfahren grob in zwei Klassen unterteilen: In die sogenannten internen Sortierverfahren und in die externen Sortierverfahren. Ein internes Sortierverfahren zeichnet sich dadurch aus, dass die zu sortierenden Daten im Speicher (z.B. in einem Array) untergebracht werden. Der Zugriff auf jeden einzelnen Datensatz ist hier leicht und vor allem schnell realisiert. Das genaue Gegenteil haben wir bei den externen Sortierverfahren, bei denen die zu sortierenden Daten auf einem (externen) Speichermedium vorliegen und der Zugriff sequentiell oder blockweise erfolgen muss.

Ich werde im Rahmen dieses Tutorials lediglich auf interne Verfahren eingehen. Es sind im Wesentlichen diejenigen Verfahren, die als die Standard-Verfahren bekannt sind:

• Selection-Sort
• Insertion-Sort
• Bubble-Sort
• Shell-Sort
• QuickSort
• Heap-Sort
• Merge-Sort

Alle diese Sortier-Verfahren machen im Endeffekt genau das Gleiche: Sie sortieren ein Array von Zahlen. Allerdings unterscheiden sie sich in drei Faktoren:

• benötigte Dauer
• benötigter Speicherplatz
• benötigte Anzahl an Vergleichen

Die Bedeutung dieser Faktoren, welche die Leistungsfähigkeit eines Verfahrens bestimmen, steigt mit der Menge der zu sortierenden Daten. Hat man nur wenige Datensätze oder sortiert nur selten, so kann es sinnvoller sein, einen einfachen Algorithmus zu Nutzen, der zwar ein wenig länger braucht, dafür aber schnell und fehlerfrei programmiert ist.
Bei weniger als zweitausend Datensätzen im Speicher macht es oftmals keinen Sinn, sich große Gedanken über einen schnellen Sortier-Algorithmus zu machen. Die Unterschiede liegen im Bereich von unter einer Sekunde.

Um die oben genannten Algorithmen in Bezug auf die drei wesentlichen Kenngrößen analysieren zu können, werde ich sie jetzt hier der Reihe nach vorstellen. Zuvor noch eine kurze Bemerkung zur den Beispiel-Codes:
Die Anzahl der zu sortierenden Elemente bezeichne ich mit dem Buchstaben N. (Dies ist die in der Fachliteratur gängige Methode). Zudem unterstelle ich als Datenfeld ein Array, welches von 1..N indiziert ist.

Selection-Sort
"Sortieren durch direktes Auswählen"
Der Selection-Sort ist einer der einfachsten Sortier-Algorithmen und läuft nach folgendem Schema ab:
Finde zuerst das kleinste Element und tausche es gegen das an erster Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und setze dies so lange fort, bis das gesamte Feld sortiert ist.

Code:

Procedure SelectionSort;
var i, j, min : Integer;
Begin
  For i:= 1 to N-1 Do
  Begin
    min:= i;
    For j:= i+1 To N Do
      If (Data[j] < Data[min]) Then min:= j;

    SwapValues( i, min);
  End;
End;

Ich werde später noch darauf eingehen, dass dieser Algorithmus nicht einer der schnellsten ist. Dennoch hat er eine Eigenschaft, die sich unter Umständen als sehr positiv erweisen kann: Jeder Datensatz wird höchstens einmal verschoben. Gerade bei sehr großen Datensätzen kann dies ein Vorteil sein.


Insertion-Sort
"Sortieren durch direktes Einfügen"
Dieser Algorithmus ist fast so einfach wie der Selection-Sort, jedoch ein wenig flexibler. Dies ist eine Methode, die Menschen oft beim Kartenspiel anwenden, um die auf ihrer Hand befindlichen Karten zu sortieren:
Betrachte die Elemente eines nach dem anderen und fügen jedes an seinen richtigen Platz zwischen den bereits betrachteten Elementen ein.
Hierzu wird erst eine Lücke geschaffen (die größeren Elemente werden nach rechts gerückt) und dann kann man auf den frei gewordenen Platz das aktuelle Element einfügen.

Code:

Procedure InsertionSort;
var i,j,v : Integer;
Begin
  For i:= 2 To N Do
  Begin
    v:= Data[i];
    j:= i;
    While (j > 1) and (Data[j-1] > v) Do
    Begin
      Data[j]:= Data[j-1];
      dec( j );
    End;
    Data[j]:= v;
  End; 
End;

Bubble-Sort
"Sortieren durch direktes Austauschen"
Dieser Algorithmus ist bestimmt in jedem Informatik-Grundkurs und jeder Informatik-Vorlesung gelehrt worden. Er gehört eindeutig zu den gemütlichen Sortier-Algorithmen. Schon bei 100.000 Elementen kann sich erst mal einen Kaffee holen, bevor dieser Algorithmus mit seiner Arbeit fertig ist. Trotzdem ist er leicht zu begreifen:
Durchlaufe immer wieder das Feld und tausche wenn nötig zwei benachbarte Elemente miteinander aus.

Code:

Procedure BubbleSort;
var i,j : Integer;
Begin
  For i:= N downto 1 Do
    For j:= 1 To i Do
      If (Data[j-1] > Data[j]) Then SwapValues( j-1, j );
End;

Shell-Sort
Der Shell-Sort ist eine Erweiterung des Insertion-Sort und setzt genau dort an, wo dieser seine Schwäche hat. Insertion-Sort ist langsam, weil stets nur benachbarte Elemente ausgetauscht werden. Steht zufälligerweise das kleinste Element ganz hinten, so werden N Vertauschungen benötigt, um es an seine richtige Position zu bringen.
Der Shell-Sort vertauscht also auch weit voneinander entferne Elemente miteinander. Diese Distanz wird als "h" bezeichnet. Der Grundgedanke besteht nun darin, dass man die Daten so umordnet, dass man eine sortierte Reihenfolge erhält, wenn man jedes h-te Element entnimmt. Lässt man dieses "h" nun gegen 1 laufen, wird nach und nach die gesamte Datenmenge sortiert.

Code:

Procedure ShellSort;
var i, j, h, v : Integer;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > N);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To N Do
    Begin
      v:= Data[i];
      j:= i;

      While ((j > h) and (Data[j-h] > v)) Do
      Begin
        Data[j]:= Data[j-h];
        dec( j, h );
      End;
      Data[j]:= v;
    End;
  Until (h = 1);
End;

Quick-Sort
Der Quick-Sort wurde 1960 entwickelt und dürfte einer der am häufigsten angewandten Sortier-Algorithmen sein. Seinen Namen verdient er der Tatsache, dass er für das Sortieren von N Elementen im Durchschnitt nur N * log (N) Operationen benötigt. (Ob das viel oder wenig ist, werden wir noch sehen) Der Quick-Sort kann sowohl rekursiv als auch iterativ programmiert werden. In rekursiver Variante belastet er den Stack-Speicher - dies kann bei großen Datenmengen zu einem Stack-Überlauf führen. In iterativer Variante läuft er zwar ein wenig langsamer, belastet dafür aber nur den Heap, welcher üblicherweise weniger beschränkt ist als der Stack.
Einen gravierenden Nachteil hat der Quick-Sort allerdings auch: Im ungünstigsten Fall benötigt er N*N Operationen, um die sortierte Reihenfolgen herzustellen. In diesem Fall zeigt er ein ähnlich schlechtes Verhalten wie der Bubble-Sort.
Das Prinzip des Quick-Sort beruht auf dem Prinzip, die Daten in Teilmengen aufzuspalten und diese unabhängig voneinander zu sortieren. Die rekursive Variante des Quick-Sort hat folgenden Rumpf:

Code:

Procedure QuickSort( l,r : Integer );
var i : Integer;
Begin
  If (r > l) Then
  Begin
    i:= Partition( l, r);
    QuickSortRekursiv( l, i-1 );
    QuickSortRekursiv( i+1, r );
  End;
End;

Von entscheidender Bedeutung ist hierbei die Prozedur "Partition". Diese muss das Datenfeld so umsortieren, dass drei Bedingungen erfüllt sind:

• das Element Daten[ i ] befindet sich an seinem endgültigen Platz
• alle Elemente, die links von i liegen, sind kleiner oder gleich dem Element Daten[ i ]
• alle Elemente, die rechts von i liegen, sind größer oder gleich dem Element Daten[ i ]

Die Methodik, nach der vorgegangen wird, um diese Ziele zu erreichen, ist von entscheidender Bedeutung für die Leistungsfähigkeit des Algorithmus. (Mehr zu diesem Aspekt später)
Diese Prozedur setzt i = r und wählt somit willkürlich das Element ganz rechts (also ist Data[ i ] = Data[ r ]) und sucht jetzt von links beginnend ein Element, welches größer als Data[ i ] ist. Nun wird von rechts beginnend ein Element gesucht, welches kleiner als Data[ i ] ist. Beide gefundenen Elemente werden vertauscht. Fährt man so fort, ist sicher gestellt, dass die Teildatenmenge sortiert ist und dass das anfangs ausgewählte Element an seiner endgültigen Position liegt. Je näher i in der Mitte des Feldes liegt, desto erfolgreicher war die Partitionierung. (An dieser Stelle werden wir später noch optimieren)

Code:

Function Partition( l,r : Integer ) : Integer;
var v,t,i,j : Integer;
Begin
  v:= Data[r];
  i:= l-1;
  j:= r;
  Repeat
    Repeat inc( i ); Until (Data[i] >= v);
    Repeat dec( j ); Until (Data[j] <= v);
    t:= Data[i]; Data[i]:= Data[j]; Data[j]:= t;
  Until (j<=i);

  Data[j]:= Data[i]; Data[i]:= Data[r]; Data[r]:= t;
  Result:= i;
End;

Man kann wie bereits erwähnt die Rekursion entfernen. Man muss jedoch noch eine Hilfs-Struktur schaffen, in welcher man sich die Indizes der Teilmengen merkt. Hier bietet sich die Datenstruktur "Stack" an. (Ich setzte diese als bekannt voraus, kann aber auf Wunsch gerne einmal tiefer auf "Stacks" eingehen)
Die rekursiven Aufrufe werden also durch Stack-Operationen ersetzt und es wird eine innere Schleife hinzugefügt, welche solange läuft, bis der Stack vollständig abgearbeitet ist.

Code:

Procedure QuickSortIterativ;
var i, l, r : Integer;     
Begin
  l:= 1; r:= N;
  Stack.Push( l ); Stack.Push( r );

  Repeat
    If (r > l) Then
    Begin
      i:= Partition( l, r );
      If (i-l) > (r-i) Then
      Begin
        Stack.Push( l );
        Stack.Push( i-1 );
        l:= i+1;
      End
      Else
      Begin
        Stack.Push( i+1 );
        Stack.Push( r );
        r:= i-1;
      End;
    End
    Else
    Begin
      r:= Stack.Pop;
      l:= Stack.Pop;
    End;
  Until StackisEmpty;
End;

Wichtig hier bei ist, dass die Indizes der Teilmengen nicht in beliebiger Reihenfolge abgelegt werden, sondern dass die Indizes der größeren Teilmenge immer zuerst auf den Stack geschrieben werden. Dies bewirkt, dass der Stack im Durchschnitt lediglich für log(N) Einträge Platz bieten muss. Im ungünstigsten Fall könnte die Belastung des Stacks N erreichen.


Heap-Sort
(Es sind jetzt Vorkenntnisse in Bezug auf Bäume und deren Repräsentation als Feld (Array) nötig. Auf Wunsch kann ich gerne einmal näher darauf eingehen)
Der Heap-Sort basiert auf der Datenstruktur "Heap". Darunter versteht man einen Binärbaum, der die sog. Heap-Bedingung erfüllt. Unter dieser Heap-Bedingung versteht man die Eigenschaft, dass der größte (oder der kleinste) Wert stets an der Wurzel steht und dass alle folgenden Knoten die Bedingung erfüllen, dass der Wert jedes Knotens größer (oder kleiner) gleich dem seiner Nachfolger ist.
Das Prinzip des Heap-Sort basiert darauf, aus den zu sortierenden Daten einen Heap zu konstruieren, dann die Elemente nacheinander vom Heap zu entfernen und nach jedem Entfernen die Heap-Bedingung wieder herzustellen.

Code:

Procedure HeapSort;
var i, k, m : Integer;
Begin
  m:= N;
  k:= m div 2;

  For i:= k downto 1 Do downHeap( i, m );

  While (m > 1) Do
  Begin
    SwapValues( 1, m );
    dec( m );
    downHeap( 1, m );
  End;
End;

Von zentraler Bedeutung ist die Methode "downHeap", welche die Heap-Bedingung wider herstellt:

Code:

Procedure downHeap( index, heapSize : Integer );
var j, k, m, v : Integer;
Begin
  k:= index;
  v:= Data[k];
  m:= heapSize;
  While (k <= (m div 2)) Do
  Begin
    j:= 2*k;
    If (j < n) Then
      If (Data[j] < Data[j+1]) Then inc( j );
    If (v > Data[j]) Then
    Begin
      Data[k]:= v;
      Exit;
    End;
    SwapValues( k, j );
    k:= j;
  End;
End;

Der Heapsort hat den eindeutigen Vorteil, dass er ohne zusätzlichen Speicher auskommt und zudem selbst im ungünstigsten Fall noch eine nahezu konstante Laufzeit von N * log(N) garantiert. (Ich gehe später darauf ein, wie dieser Umstand zu bewerten ist)

Merge-Sort
Der Merge-Sort sortiert eine Datenmenge, indem er sie in Hälften teilt, diese dann (rekursiv) sortiert und anschließend zusammenfügt. Der Mergesort hat eine Eigenschaft, die als wesentlicher Vorteil gesehen werden kann: Man kann ihn so implementieren, dass der Zugriff auf die Daten hauptsächlich sequentiell erfolgt. Zum Beispiel ist der Mergesort ein gern genutztes Sortier-Verfahren für verkettete Listen, bei denen ein sequentieller Zugriff die einzig mögliche Zugriffsart ist. Leider hat er aber auch einen Nachteil: Er benötigt proportional zu N weiteren Speicher. (Im Code-Beispiel durch 'HilfsArray' dargestellt)

Code:

Procedure MergeSort( l, r : Integer );
var i, j, k, m : Integer;
Begin
  If (l < r) Then
  Begin
    m:= (r+l) div 2;

    MergeSort( l, m  );
    MergeSort( m+1, r );

    For i:= l To m Do HilfsArray[i]:= Data[i];
    i:= l;

    For j:= m+1 To r Do HilfsArray[r+m+1-j]:= Data[j];
    j:= r;

    For k:= l To r Do
    Begin
      If (HilfsArray[i] < HilfsArray[j]) Then
      Begin
        Data[k]:= HilfsArray[i];
        inc( i );
      End
      Else
      Begin
        Data[k]:= HilfsArray[j];
        dec( j );
      End;
    End;
  End;
End;

Das war also ein erster Überblick über die Standard-Sortierverfahren. Ich hoffe, dass ich mich einigermaßen verständlich ausgedrückt habe. Für Fragen und Anmerkungen bin ich natürlich jederzeit offen.

Im nächsten Teil werde ich die vorstellten Algorithmen hinsichtlich der Laufzeit analysieren und vergleichen. In diesem Zusammenhang werde ich auch Varianten des Quick- und Heap-Sorts vorstellen, welche Laufzeit drastisch verbessern. Dann wird es auch das vollständige Programm-Listing zum Download geben.

Grüße,
Daniel

[Daniel]

Nachdem ich im letzten Teil die Standard-Algorithmen in gängigen Implementationen vorgestellt habe, will ich jetzt dazu kommen, diese zu vergleichen.
Als Basis habe ich ein Array mit 100.000 Elementen, welches einmalig mit Zufallszahlen gefüllt wird. Dieses Array wurde gesichert und für jeden Sortier-Algorithmus in genau der selben Form wieder hergestellt, so dass alle hier behandelten Algorithmen die gleiche Ausgangs-Situation vorfanden.
Verglichen werden jeweils die Laufzeit sowie die benötigte Anzahl an Vergleichen:

Bubble-Sort
Dauer: 74.157 ms
Anzahl Vergleiche: 5 * 10^9

Selection-Sort
Dauer: 42.341 ms
Anzahl Vergleiche: 5 * 10^9

Insertion-Sort
Dauer: 20.359 ms
Anzahl Vergleiche: 2,5 * 10^9

Shell-Sort
Dauer: 80 ms
Anzahl Vergleiche: 7.146.727

Quick-Sort (Rekursiv)
Dauer: 30 ms
Anzahl Vergleiche: 2.224.657

Quick-Sort (Iterativ)
Dauer: 71 ms
Anzahl Vergleiche: 2.224.657

Heap-Sort
Dauer: 65 ms
Anzahl Vergleiche: 2.984.590

Merge-Sort
Dauer: 40 ms
Anzahl Vergleiche: 1.668.946

Wie man unschwer erkennen kann, bilden der Bubble-, der Selection- und der Insertion-Sort die Schlusslichter.
Für diese Anzahl an Elementen spielt es ansonsten kaum eine Rolle, für welchen Algorithmus man sich entscheidet. Das könnte man zumindest meinen... Interessant wird es jetzt, wenn man sich die Anzahl an benötigten Vergleichen ansieht. Dieser Wert wird genau dann wichtig, wenn der Zugriff auf die benötigten Elemente Zeit kostet. In solch einem Szenario wäre es wichtig, die Vergleiche zu minimieren, um so die gesamte Laufzeit zu drücken. Folgende Variationen des Heap- und des Quicksort bringen diesbezüglich weitere Vorteile:

Heap-Sort (Optimiert)
Dauer: 50 ms
Anzahl Vergleiche: 1.560.387

Quick-Sort (Rekursiv / Optimiert)
Dauer: 20 ms
Anzahl Vergleiche: 1.628.846

Was verbirgt sich hinter diesen Varianten? Nun - der Heapsort hält sich lange damit auf, die Heapbedingung wieder herzustellen. Zu diesem Zweck schreibt er die Werte immer ganz nach unten an den Heap und bringt die von dort aus in die richtige Position. Es hat sich aber gezeigt, dass es im Mittel reicht, nur die halbe Strecke zurück zu legen und die Werte von der Mitte aus an die richtige Position zu bringen - sei es nun nach oben oder unten.

Code:

Procedure downHeapRisky( index, heapSize : Integer );
var ix, son1, son2, ixson : Integer;
Begin
  ix:= index;
  While (ix <= (heapSize div 2)) Do
  Begin
    son1:= 2 * ix;
    son2:= son1 + 1;

    If (son2 > heapSize) or (Data[son1] > Data[son2]) Then
      ixson:= son1
    Else
      ixson:= son2;

    SwapValues( ix, ixSon );
    ix:= ixSon;
  End;
  upHeap( index, ix );
End;

Procedure upHeap( index, heapSize : Integer );
var temp, upix, upix2 : Integer;
Begin
  temp:= Data[heapSize];
  upix:= heapSize;
  upix2:= upix div 2;

  While ((upix2 >= index) and (Data[upix2] < temp)) Do
  Begin
    SwapValues( upix, upix div 2 );
    upix:= upix div 2;
    upix2:= upix div 2;
  End;
  Data[upix]:= temp;
End;

Procedure HeapSortFast;
var size, i : Integer;
Begin
  size:= AnzahlElemente;

  For i:= (size div 2) downTo 1 Do downHeapRisky( i, size );

  For i:= 1 To size Do
  Begin
    SwapValues( 1, size-i+1 );
    downHeapRisky( 1, size-i );
  End;

End;

Und was wurde beim Quicksort geändert? Der wesentliche Vorteil des Quicksorts liegt darin, dass er die Daten über große Entfernungen hin austauschen kann. (Aus genau dem konträren Verhalten heraus ist der Bubble-Sort so langsam; er tauscht lediglich benachbarte Elemente aus). Je näher der Quicksort dem Ende kommt, desto häufiger hat er die Daten geteilt und desto kleiner werden die Teilmengen. Hier wird der Quicksort mehr und mehr ineffizient, da der Verwaltungsaufwand für die Rekursion oder den eigenen Stack deutlicher ins Gewicht fallen. Also hört man einfach auf, wenn die Größe der Mengen eine Größe von beispielsweise 25 erreicht haben. Dann setzt man einen Insertion-Sort ein, der bei kleinen vor-sortierten Teilmengen unschlagbar schnell ist. In dieser Kombination erreicht man den o.g. Vorteil.

Code:

Procedure InsertionSortForQuickSort;
var i,j,v : Integer;
Begin

  For i:= ErstesElement+1 To LetztesElement Do
  Begin
    v:= Data[i];
    j:= i;
    While (j > 1) and (Data[j-1] > v) Do
    Begin
      Data[j]:= Data[j-1];
      dec( j );
    End;
    Data[j]:= v;
  End;
End;

Procedure QuickSortOptimal( l, r : Integer );
var i, j, p, q, v, k : Integer;
Begin
  i:= l-1;
  p:= l-1;
  j:= r;
  q:= r;
  v:= Data[r];

  If (r - l) > 20 Then
  Begin

    Repeat
      inc( i );
      While (Data[i] < v) Do
      Begin
        inc( i );
      End;

      dec( j );
      While (v < Data[j]) Do
      Begin
        dec( j );
        If (j < l) Then Break;
      End;

      If (i >= j) Then Break;
      SwapValues(i, j);

      If (Data[i] = v) Then
      Begin
        inc( p );
        SwapValues( p, i );
      End;

      If (Data[j] = v) Then
      Begin
        dec( q );
        SwapValues( j, q );
      End;
    until (j < i);

    SwapValues( i, r );
    j:= i-1;
    inc( i );

    k:= l;
    While (k < p) Do
    Begin
      inc( k );
      dec( j );
      SwapValues( k, j );
    End;

    k:= r-1;
    While (k > q) Do
    Begin
      dec( k );
      inc( i );
      SwapValues( i, k );
    End;

    QuickSortOptimal( l, j);
    QuickSortOptimal( i, r);
  End;
End;

Ich hoffe, dass der eine oder andere ein paar für ihn brauchbare Infos herausziehen konnte (wenngleich es natürlich ein etwas spezielleres Thema ist... :wink:)

Grüße,
Daniel

[Daniel B]

Hi,

hoffentlich ist dir die Tinte in der Tastatur nicht ausgegegangen. :mrgreen:
Könntest du das vielleicht zippen und auch zum Download anbieten? Vielleicht sigar pdf, falls du es hast.

[Tpercon]

Hi :hi:

Ich wollte den ShellSort mal aus Spaß zum Sortieren einer ListView nehmen. Warum funktioniert der Code nicht?

Code:

var i,j,h:integer;
    v:TListItem;
    begin
     h:=1;
     Repeat
      h:=(3*h)+1;
     Until (h>ListView1.Items.Count-1);
     Repeat
      h:=(h div 3);
      For i:=(h+1) To ListView1.Items.Count-1 Do
       Begin
        v:=ListView1.Items.Item[i];
        j:=i;
        While ((j>h) and (ListView1.Items.Item[j-h].Caption>v.Caption)) Do
         Begin
          ListView1.Items.Item[j]:=ListView1.Items.Item[j-h];
          dec(j,h);
         End;
        ListView1.Items.Item[j]:=v;
       End;
     Until (h=1);
    end;

[Daniel]

Es hat offenbar Probleme mit den Objekt-Referenzen gegeben. Wenn man sich lediglich auf die Captions beschränkt, dann geht es. Zudem arbeitet die von mir vorgestellte Version auf einem Datenbestand, der mit dem Index 1 anfängt. Also musst Du die Indices aller Zugriffe auf die ListItems um 1 erniedrigen.

Code:

var i,j,h:integer; 
    v:TListItem;
    begin
     v:= TListItem.Create( ListView1.Items );  // den habe ich mal erzeugt
     h:=1;
     Repeat
      h:=(3*h)+1;
     Until (h>ListView1.Items.Count-1);
     Repeat
      h:=(h div 3);
      For i:=(h+1) To ListView1.Items.Count-1 Do
       Begin
        v.Caption:=ListView1.Items.Item[i-1].Caption;
        j:=i;
        While ((j>h) and (ListView1.Items.Item[j-h-1].Caption>v.Caption)) Do
         Begin
          ListView1.Items.Item[j-1].Caption:=ListView1.Items.Item[j-h-1].Caption;
          dec(j,h);
         End;
        ListView1.Items.Item[j-1].Caption:=v.Caption;
       End;
     Until (h=1);
     v.Free;
    end;

In dieser Fassung funktioniert der Algorithmus - jetzt muss man sich nur noch um eine saubere Behandlung der Objekte kümmern.

Grüße,
Daniel

[Udontknow]

Hallo, Daniel! :)

Ich habe mir mal den Quicksort zu Gemüte geführt und treffe da auf ein paar Probleme, vielleicht kannst du mir weiterhelfen:


Ich bekomme beim Ausführen den Hinweis "Listenindex überschreitet das Maximum" (habe anstelle eines Arrays ein TList-Objekt, habe also deine Routinen dementsprechend angepasst).

Du hast ja die Routinen Quicksort und Partition gepostet.
Bei der Funktion Partition glaube ich einen Fehler entdeckt zu haben.

Du initialisierst folgende Werte :

Code:

  
i:= l-1; 
j:= r;

i entspricht dem ersten Element in der Menge -1; Da du sofort in einer repeat-until-Schleife um 1 erhöhst, erhälst du dann als erstes den Index des ersten Elementes.
Wieso tust du das aber nicht mit j? Du willst ja anscheinend zunächst das letzte Element erhalten, da aber erstmal wieder in einer Repeat-Until-Schleife Dec(j) erfolgt, setzt du doch hier (fälschlicherweise?) beim vorletzten Element an, oder?

Nachdem ich also die Zeile "j:=r" durch "j:=r+1" ersetzt hatte, traten keine Fehler mehr auf, die Liste ist dann aber immer noch nicht komplett sortiert. Hast du auf Anhieb ne Idee, woran das liegen könnte?

Ich poste mal meine Partition-Routine, vielleicht hilft´s ja:

Code:

function TStempIDComponentList.Partition(l, r: Integer): Integer;
var v,i,j : Integer;
var t:Pointer;
Begin
  v:= Items[r].ID;
  i:= l-1;
  j:= r+1;
  Repeat

    Repeat
      inc( i );
    Until (Items[i].ID >= v);

    Repeat
      dec( j );
    Until (Items[j].ID <= v);

    t:= Items[i];
    Items[i]:=Items[j];
    Items[j]:= t;

  Until (j<=i);

  Items[j]:= Items[i];
  Items[i]:= Items[r];
  Items[r]:= t;

  Result:= i;
End;

Cu & thx im voraus, :D
Udontknow

[Udontknow]

Hallo, ich bins nochmal! :D

Irgendwo war da noch der Wurm in der Partition-Routine. :?:
Warum setzt du das vergleichende Element eigentlich auf das rechte Ende der Folge? In meiner Algorithmus-Beschreibung steht, das das mittlere Element für den Vergleich ausgewählt werden muss...

Naja, ich habe es noch einmal neu aufgesetzt, allerdings mit while-Schleifen anstelle von Repeat-Until-Konstrukten. So klappts.

In diesem Fall sortiere ich Objekte, die sich in einer Liste befinden und von meiner Klasse TStempIDComponentList verwaltet werden. ich sortiere nach dem Attribut ID der einzelnen Objekte.

Code:

procedure TStempIDComponentList.SwapValues(Index1, Index2: Integer);
var P:Pointer;
begin
  P:=Items[Index1];
  Items[Index1]:=Items[Index2];
  Items[Index2]:=P;
end;

function TStempIDComponentList.Partition(l, r: Integer): Integer;
var x,i,j : Integer;
begin
  //Mittleres Element x bestimmen
  x:=r+l div 2;

  //Elemente von aussen nach innen durchgehen & evt. vertauschen
  i:=l;
  j:=r;

  //Solange vorgehen, bis Grenzen angenähert
  while (i<j) do
  begin
    //Äußerstes Element der linken Seite bestimmen, das verschoben werden muss 
    //(Vergleich des  Feldes ID der Objekte)
    while (Items[i].ID<Items[x].ID) do
      Inc(i);
    //Äußerstes Element der rechten Seite bestimmen, das verschoben werden muss 
    //(Vergleich des  Feldes ID der Objekte)
    while (Items[j].ID<Items[x].ID) do
      Dec(j);

    //Werte vertauschen
    SwapValues(i,j);
  end;

  Result:=i;
end;

Cu, :D
Udontknow

[Daniel]

Zitat:

Zitat von Udontknow

Warum setzt du das vergleichende Element eigentlich auf das rechte Ende der Folge? In meiner Algorithmus-Beschreibung steht, das das mittlere Element für den Vergleich ausgewählt werden muss...

.. das haben mich meine Berater die letzten zwei Tage vor dem Schreiben des Tutorials auswendig lernen lassen. :mrgreen:
Nein - mal im Ernst: Ich greife das Thema morgen nochmal auf; heute habe ich mein Hirn offenbar schon überlastet. :wink:

Grüße,
Daniel

[Daniel]

Hallo,

bei der Partitionierung geht es ja darum, sich ein Element aus der Datenmenge zu greifen und anschliessend die Datenmenge so zu sortieren, dass alle Elemente, die kleiner als das gewählte Element sind, links davon liegen und alle Elemente, die grösser als das gewählte Element sind, rechts davon liegen.

Der Quicksort arbeitet um so effizienter, je näher das gewählte Elemente an der Mitte der Datenmenge liegt.

Wenn Du nur ein einzelnes Element herausgreifst und wir mal davon ausgehen, dass Du eine unsortierte Datenmenge vorliegen hast, so ist es völlig unerheblich, welches Element Du herausgreifst. Die Wahrscheinlichkeit ein geeignetes Element zu finden, ist für das erste, letzte und mittlere Element gleich gross.

Eine Technik, den Vorgang zu optimieren, wäre der "Median von Dreien", nach der Du Dir drei Elemente herausgreifst und deren mittleres Element auswählst.


Grüße,
Daniel

[Udontknow]

Wir müssen uns nochmal mit dem Fehler in der Routine "Partition" beschäftigen.

Was ist mit der Initialisierung "j:=r"?

Deine Funktion "Partition" schlägt fehl, wenn das letzte Element Data[r] die kleinste Wertigkeit hat.

Nimm mal folgende Zahlenfolge an :

Data[1]:=1200;
Data[2]:=1100;
Data[3]:=1000;

Führe nun Partition[1,3] durch.
Die Initialisierung belegt dann

v=Data[r]=1000,
i=l-1=0
und j=r=3.

Nachdem i einmal inkrementiert und dann die Abbruchbedingung Data[i]>=v) erfüllt wurde, gerätst du in eine Endlosschleife, die j immer weiter senkt:
Du senkst zunächst j um 1. Ab diesem Zeitpunkt ist (zumindest innerhalb der Arraygrenzen) deine Abbruchbedingung Data[j]<=v gar nicht mehr erfüllbar, da eben der niedrigste Wert der Zahlenfolge das letzte Element (r) ist, du aber eine Prüfung immer erst beim vorletzten Element ansetzt!
Bei einem TList-Objekt wie bei mir ist sowas halb so schlimm, ich bekomme dann eine Exception, bei einem Array aber "sortierst" du plötzlich Speicherbereiche, die gar nicht zum Array gehören (wenn z.B. zufälligerweise Data[-5043]=900 ist, tauscht du dann an dieser Stelle die Werte aus :wink: ).

Bei einer Initialisierung mit "j:=r+1" wäre das natürlich dann korrekt.

Was meinst du?

Cu,
Udontknow

[Daniel]

Ahem ... Du hast natürlich recht. Da ist noch ein Wurm drin. Ich bin gerade dabei, dieses Tutoral samt Quellcodes zu überarbeiten. Ich gebe Bescheid, wenn ich soweit bin.

:oops: :oops: :freak: :oops: :oops:


Grüße,
Daniel

[Torsten72]

Ich muß sagen, daß die Beiträge sehr hilfreich sind. Gerade, wenn man einen Sortieralgorithmus für einen bestimmten Zweck sucht, sind die Vergleiche und Optimierungsvorschläge sehr nützlich.
Nun habe ich aber ein spezielles Problem. Ich möchte gerne eine Liste sortieren, die aber nicht ganz in den vom Programm nutzbaren Speicher passt. Das heißt, daß nach wenigen bis einigen hundert Einträgen ein Speicherseitenwechsel notwendig wird. Die einzelnen Listeneinträge können zudem bis zu 3KB groß sein. Welchen Algorithmus nehme ich am besten? Ich denke der Quicksort mit Optimierung, wie er hier dargestellt wird, ist noch am besten geeignet, weil er auch für große Datenmengen am schnellsten ist. Allerdings nur dann, wenn man auf verkettete Listen zurückgreift. Bei verketteten Listen ergibt sich aber das Problem, aus einem Bereich jeweils den mittleren Eintrag zu finden, weil ja die Position eines Eintrags in der Liste nicht der tatsächlichen Position in der Liste entspricht. Das ist nur ganz zu Anfang so, wenn die Liste neu erstellt wird. Man müßte also eigentlich, jedesmal, wenn man den mittleren Eintrag sucht, die verkettete Liste sequentiell so lange durchlaufen, bis man beim mittleren Eintrag angekommen ist. Aber gerade bei großen Datenmengen (100.000 Einträge zu je 508 Byte Größe z.B.) wo dann auch immer noch ein Speicherseitenwechsel zwischendurch notwendig wird, bei dem die Daten eventuell auch noch von Festplatte eingelagert werden müssen, bremst das doch den ganzen Algorithmus aus. Oder sehe ich das falsch? Wie kann man denn, vielleicht mit einem Trick, den mittleren Eintrag einer verketteten Liste schnell finden, also ohne das sequenzielle Suchen?
Oder gibt es vielleicht noch andre effektivere Ansätze zur Sortierung solcher von mir beschriebener Datenmengen?

Torsten

[S - tefano]

Hi Daniel,

sehr sehr nützlich, was du da "offenbarst". Ich hätt vor allen Dingen nie gedacht dass es so viele verschiedene Möglichkeiten gibt, Arrays zu sortieren.
Jetz hätt ich zwei Fragen:
1.: Bin ich nur zu blöd, oder hast du den QuickSortRekursiv weggelassen? Der würd mich mal interessieren, weil der laut deinen "Benchmarkwerten" ja doch um einiges schneller ist als der itverative, obwohl er genauso viele Vergleiche macht.
2.: Hast dus aufgegeben, oder dauert das wirklich so lange, dieses Tutorial zu überarbeiten?

Bis dann,

S - tefano

[Daniel]

hm. Das ist mir jetzt direkt unangenehm. :oops: Ich habe aufgrund verschiedener laufender Projekte diese Algorithmen ein wenig aus den Augen verloren. Ein neues und erweitertes Delphi-Projekt mit diesen Algorithmen liegt zu dreiviertel fertig auf meiner Festplatte. Die Quicksorts werden dann auch alle vollständig sein.

Ich kann aber zum gegenwärtigen Zeitpunkt kein Datum der Fertigstellung angeben. Leider. :?

[S - tefano]

Hi,

naja, solange ich mich (und die anderen sich) drauf freuen kann/können, bald (oder halt irgendwann) das neue Tutorial mit vollständigem QuickSort zu sehen, ist es ja nicht so schlimm.
Is schönmal schön dass das Ganze auch nach "so langer Zeit" nicht einstaubt sondern wenigstens halbwegs in Arbeit ist.

Bis dann,

S - tefano

[ShadowCaster]

ein kleiner Tipp: Mir ist aufgefallen dass in den meisten guten quicksortimplementierungen DIV verwendet wird. Leider ist DIV sehr langsam. Shr 1 (den Wert 1 Byte rechts schieben) ist 5-10 mal schneller. Bei großen Arrays kann man damit schon eine ganze Menge einsparen. Ein Kumpel von mir (der ist ein delphi- und asmfreak) hat das getestet. INC und DEC sind auch langsamer als i := i + 1; oder i := i - 1; z.B. Das bringt zwar sogut wie nichts, aber schneller ists so trotzdem.

Scheinbar wird in sämtlichen Delphialgorithmen von quicksort div verwendet. Das kann ich nicht verstehen. Egal ;)

Ansonsten frag ich mich, obs nicht auch eine Assemblerimplementierung von Quicksort gibt. Schneller sein dürfte die aber wohl kaum.

Die Tausche-Methode kann man in Quicksort auch durch die drei direkten Befehle ersetzen. So hat man 2 Codejumps weniger für den Prozessor pro Durchlauf.

Alles in allem lässt sich Quicksort so wie es oben ist noch ganz schön optimieren. :!:

[sakura]

Zitat:

Zitat von ShadowCaster

Leider ist DIV sehr langsam. Shr 1 (den Wert 1 Byte rechts schieben) ist 5-10 mal schneller.

Diese Aussage ist spätestens seit Delphi 5 nicht haltbar, da DIV durch den Compiler wenn möglich durch SAR ersetzt wird (ähnlich SHR) und damit erst einmal nicht länger braucht (3 Taktzyklen).

Zitat:

Zitat von ShadowCaster

INC und DEC sind auch langsamer als i := i + 1; oder i := i - 1; z.B. Das bringt zwar sogut wie nichts, aber schneller ists so trotzdem.

Falsch. I := I + 1 wird durch den Compiler in Inc (Register) umgewandelt und ist damit gleich schnell wie Inc(I).

...:cat:...

[Daniel]

Hallo,

es ging ja hierbei auch nicht darum, die vermeintlich ideale Delphi-Implementation zu finden, sondern den Algorithmus als solchen zu verbessern.



(Ob ich in diesem Leben noch jemals die Zeit finden werde, dieses Tut zu überarbeiten?... :roll:)

[ShadowCaster]

naja, habs ja nur gut gemeint :) mein Kumpel hat das nur in einer großen Schleife getestet und bei ihm war i := i + 1; minimal schnell in delphi als inc(i) bei 100000 Schleifendurchläufen. Er hat Delphi 4. Das mit dem Div hat er auch getestet und da wars sehr groß, der Unterschied. Kann sein, dass er sich irrt. Jedenfalls hab ich heut wieder ne Menge dazugelernt.

[sakura]

Minimal werden unter Windows die Zeitunterschiede immer sein, wegen dem "Multitasking" Man kann nicht alles beeinflussen. Das mit DIV kann gut sein, im D5 Compiler wurde viel an den Optimierungen gearbeitet.

...:cat:...

[ShadowCaster]

Ja, das mit den Zeitunterschieden wegen Multitasking ist mir bekannt. Naja, egal. Sorry, dass ich delphi 4 sagte, Muss mich vertippt haben. Meinte Delphi 7. :mrgreen:

[Luckie]

Ab D5 macht Delphi aus i := i+1 und Inc(i) den gleichen Maschinen Code.

[ShadowCaster]

ok :) werds mir merken. jetzt weiß ich worauf ich bei den Sortieralgos achten muss.

[Anänger]

Ich soll für Schule einen möglichst gute Sortierfunktion programmieren Ich entschieht mich für den Quick-Sort.

Nun verstehe ich aber nicht, was es mit dem Stack auf sich hat. :roll:
Ich hatte den Text erstmal nur kopiert um die Vorgänge mal zu studieren.
Nun läuft die Sortierung nicht, da er Stack nicht kennt.
Was ist das, wozu dient es und was muss man damit machen?
Könnte mir jemand das mal erklären?

[Gabriel]

kann mir einer mal eben die Befehle, die zum Zeitmessen der einzelnen Sortierverfahren gebraucht werden nennen?? wär sehr nett! Muss am Mittwoch mein Programm abgeben.

[Bobator]

:hi: hiho,

das Thema Sortieralgorithmen haben wir lang und breit in der schule behandelt. Auf meiner Homepage findest du unter Projekte->Sortierprog ein Programm, welches die Sortieralgorithmen vergleicht und sonst noch andere Features hat. Schaus dir mal an und sag wie es ist.

[Nalincah]

In welcher Unit finde ich die Procderue "SwapValues"??

[Matze]

Ich denke mal, die procedure SwapValues müsste so ungefähr aussehen:

Delphi-Quellcode:

procedure SwapValues(var Zahl1, Zahl2: real);
var h: real;
begin
  h := Zahl1;
  Zahl1 := Zahl2;
  Zahl2 := h;
end;

Aber ohne Gewähr, nur aus dem Bauch raus. ;)

[Luckie]

wäre schön, wenn es das ganze mal als PDF zum Downloaden und drucken gäbe. ;)

[MaBuSE]

Zitat:

Zitat von Luckie

wäre schön, wenn es das ganze mal als PDF zum Downloaden und drucken gäbe. ;)

Wofür ist den der [PDF] Button ganz oben auf dieser Seite?

Der hat die URL: http://www.delphipraxis.net/dpX_pdf.php?t=344

Ist eine sehr gute Funktion, oder? :mrgreen:

[Alexander Roth]

Zitat:

Zitat von Daniel

Delphi-Quellcode:

Procedure ShellSort;
var i, j, h, v : Integer;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > N);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To N Do
    Begin
      v:= Data[i];
      j:= i;

      While ((j > h) and (Data[j-h] > v)) Do
      Begin
        Data[j]:= Data[j-h];
        dec( j, h );
      End;
      Data[j]:= v;
    End;
  Until (h = 1);
End;

Unten das habe ich von Alexander Franz (http://www.alexander-franz.de):

Delphi-Quellcode:

function TMainFrm.shellSort(zahlen : IntArray): Int64;
var
  i, j, k, tmp: Integer;
  n : Int64;
const
  h : Array[0..15] of Integer = (1391376, 463792, 198768, 86961, 33936, 13776,
                                4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1);
begin
  for k:=0 to Length(h)-1 do
  begin
    for i:=h[k] to Length(zahlen) do
    begin
      j := i;
      tmp := zahlen[j];
      while ((j>h[k]) AND (tmp<zahlen[j-h[k]])) do
      begin
        zahlen[j] := zahlen[j-h[k]];
        Dec(j, h[k]);
        Inc(n);
      end;
      zahlen[j] := tmp;
    end;
  end;
  Result := n;
end;

Ich kopiere nur äußerst ungern einen Code und will ihn gern immer selbst verstehen:
Also Shellsort habe ich von der Logik her kapiert:
1. halbe Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
2. viertel Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
3.....
...

Also die 2 äußeren Schleifen sind mir klar. Aber was die innere da soll? Das ist doch einfach nur eine Bedingung, wenn die eine größer ist als die andere dann vertausche, ansonsten mache nix.
Und die Bedingung j>h[k]ist auch irgendwie komisch, man hat doch in der for schleife davor genau das festgelegt, dass diese Bedingung immer erfüllt ist.
Und es kann ja nix bingen Dec(j, h[k]); für den nächsten Durchlauf zu beschreiben, denn j wird ja wieder i zugewiesen. Es kann also nur für die innerste Schleife relevant sein. Doch was macht die da. Die macht doch die Bedingung (j>h[k]) lediglich unerfüllt. Damit läuft die innerste Schleife immer nur genau 1 mal durch. Damit kann man es auch in einer if Bedingung schreiben.

Wisst ihr eine Erklärung?

[Lee500]

Hiho,

Ich hab mich ma an den ShellSort algorythmus gewagt. Er sortiert jetzt wunderbar, bis auf den letzten Datensatz.

Delphi-Quellcode:

Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs)-1);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs)-1 Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;

TRun ist ein eigenes record mit ein paar variablen, wie z.B. das benutzte sumtime. Ich will also die array-Datensätze des arrays Runs nach sumtime sortieren. Er sortiert wie gesagt alles, nur den letzten Datensatz nicht. Es wäre wirklich toll wenn ihr meinen Denkfehler finden würdet.

Gruß Lee500

[Larsi]

Mach ein neues Thema auf. Hier darfst du nur Fragen und Anregungen und Kritik über Daniels Tut loswerden.

[Lee500]

Das ist doch eine Frage zum Tut. Im Tut steht ja der ShellSort-Algorytmus, der den letzten Datensatz nicht berücksichtigt. So gesehen ist es eine Frage zum Tut.

[marabu]

Hallo,

@Lee500: Du musst fremden Code immer an deine Bedürfnisse anpassen. Daniel verwendet ein Array Data[1..N], für dein Array hingegen gilt Low(Runs) = 0.

@Larsi: Was du da machst ist falsch. Wenn dir etwas auffällt, was nicht in Ordnung ist, dann benachrichtige einen Mod.

Freundliche Grüße

[Lee500]

Hi,

@marabu ich habe ja bereits überall Length(Runs)-1 und das ganze so angepasst wie im Post von Daniel mit der TListBox. Von daher müsste es so funktionieren. Wenn ich das nicht berücksichtigt hätte, wäre im übrigen der erste Datensatz der, der nicht mitsortiert würde.

Hab das Problem jetzt behoben:

Delphi-Quellcode:

Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs));

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs) Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;

So funktioniert es wunderbar.

Gruß Lee500

[zeustates]

hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang

[Delphi-Laie]

Zitat:

Zitat von zeustates (Beitrag 1318429)

hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang

Sigsev? Das kenne ich von Lazarus(-Compilaten). Benutzt Du Lazarus?

Mergesort benutze ich in rekursiver und "halb-rekursiver" Form in meinem Sortierkino, es läuft auch mit Lazarus-Compilaten.