Verschiedene Sortier Algorithmen (unter anderem Quicksort)

[Tarry]

So,
hier eine Liste mit 4 verschiedenen Sortier Algorithmen:

Delphi-Quellcode:

unit SortAlgos;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

procedure WertTauschen(var Werte: Array of Integer; StelleA, StelleB: Integer);
procedure BubbleSort(var dummy: Array of Integer; n : integer);
procedure Sortiere_Einfuegen(var dummy: Array of Integer; n : integer);
procedure Sortiere_Auswahl(var dummy: Array of Integer; n : integer);
procedure QuickSort(var dummy: Array of Integer; erstes,letztes: integer);

implementation


procedure WertTauschen(var Werte: Array of Integer; StelleA, StelleB: Integer);
var tempI: integer;
begin
tempI := Werte[StelleA];
Werte[StelleA] := Werte[StelleB];
Werte[StelleB] := tempI;
end;

procedure BubbleSort(var dummy: Array of Integer; n : integer);
var i,j : integer;
begin
for i := 0 to n do
  for j := 0 to n - 1 - i do   {ListBox beginnt bei Zeile 0}
    if dummy[j] > dummy[j+1] then
    WertTauschen(Dummy,j,j+1);
end;

procedure Sortiere_Einfuegen(var dummy: Array of Integer; n: integer);
var i,j,hilf: integer;
begin
  for i := 1 to n do {Änderung gegenueber dem Arbeiten auf ARRAY: i:=1}
    begin
      j := i - 1;
      hilf := dummy[i];
      while ((j >= 0) and (hilf < dummy[j])) do  {j<=0}
        begin
          dummy[j+1] := dummy[j];
          dec(j);
        end;
      dummy[j+1] := hilf;
    end
end;

procedure Sortiere_Auswahl(var dummy: Array of Integer; n: integer);
var i,j,tausch_index, min: integer;
begin
  for i := 0 to n - 1 do
   begin
    min := dummy[i];
    tausch_index := i;
    for j := i + 1 to n do
    begin
      if min > dummy[j] then
      begin
        tausch_index := j;
        min := dummy[j]
      end;
    end;
    if tausch_index > i then WertTauschen(Dummy,i,tausch_index);
   end
end;

procedure QuickSort(var dummy: Array of Integer; erstes,letztes: integer);
var vonLinks, vonRechts, mitte, vergleichsElement: integer;
begin
if erstes < letztes then   {mind. 2 Elemente}
begin                      {Zerlegung vorbereiten}
  mitte := (erstes + letztes)div 2;
  vergleichsElement := dummy[mitte];
  vonLinks := erstes;
  vonRechts := letztes;
  while vonLinks <= vonRechts do {noch nicht fertig zerlegt?}
  begin
    while dummy[vonLinks] < vergleichsElement do  {linkes Element suchen}
    vonLinks := vonLinks + 1;
    while dummy[vonRechts] > vergleichsElement do {rechtes Element suchen}
    vonRechts := vonRechts - 1;
    if vonLinks <= vonRechts then
      begin
        WertTauschen(Dummy,vonLinks,vonRechts);  {Elemente tauschen}
        vonLinks := vonLinks + 1;
        vonRechts := vonRechts - 1;
      end;
  end;
  Quicksort(dummy,erstes,vonRechts); {li. und re. Teilfeld zerlegen}
  Quicksort(dummy,vonLinks,letztes);
end;
end;

end.

Gruß
Tarry

[hathor]

Bei manchen DELPHI-Versionen ist ein Sortierbeispiel dabei:

suche unter DEMOS, THREADS...

[omata]

Hier mal eine überarbeitete Version...

[shmia]

Hier gibt es ebenfalls Sortieralgorithmen in der Code-Library.
Allerdings ist der Code objektorientiert und man kann im Prinzip alles (arrays, Stringlisten, Objektlisten) sortieren.
Ausserdem wird die Anzahl der Vergleiche und Vertauschungen mitgezählt; diese Werte sind nützlich, um die Leistungsfähigkeit eines Sortieralgorithmus zu beurteilen.