Bucketsort history menue scroll up

Bucketsort: 1. Variante
Gänzlich verschieden zu den bisher besprochenen Sortieralgorithmen arbeitet Bucketsort. Das Grundprinzip besteht darin, dass das Feld (Primärfeld) nicht in sich selbst sortiert sondern zwischenzeitlich auf ein zweites Feld (Sekundärfeld) abgebildet wird. Dabei werden die Elemente während des ersten Felddurchlaufs in Buckets (engl. Eimer, Behälter) einsortiert und anschließend während eines zweiten Durchlaufs wieder in das Ausgangsarray zurückgeschrieben.
Bucketsort in seiner einfachsten Form könnte wie folgt aussehen.

Handelt es sich bei den zu sortierenden Elementen wie in unserem Falle um Integerzahlen, so kann das Sekundärfeld einfach mitzählen, wie häufig eine Zahl im Primärfeld auftritt, z.B. bucket[12]=3 oder bucket[13]=0.
  

const
  size = 19;

type
  feld = array[0..size] of integer;

const
  zahl_k: feld = (96,12,59,85,99,55,8,42,2,59,34,18,12,85,48,22,71,12,16,8);

var
  Form1: TForm1;
  zahl: feld;
  bucket: array[0..99] of byte;

implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
var i, j: byte;
begin
  zahl:=zahl_k;
  for i:=0 to size do lstUnsort.Items.Add(IntToStr(zahl[i]));
  for j:=0 to 99 do bucket[j]:=0;   // Bucket-Feld initialisieren
end;

procedure TForm1.btnOKClick(Sender: TObject);
var i, j: byte;
begin
  // Elemente auf die Buckets verteilen
  for i:=0 to size do bucket[zahl[i]]:=bucket[zahl[i]]+1;
  // Elemente wieder einsammeln
  i:=0;
  for j:=0 to 99 do
  begin
    while bucket[j]>0 do
    begin
      zahl[i]:=j;
      bucket[j]:=bucket[j]-1;
      i:=i+1;
    end;
  end;
  lstSort.Clear;
  for i:=0 to size do lstSort.Items.Add(IntToStr(zahl[i]));
end;
 
Vorteil von Bucketsort:
Da das zu sortierende Feld nicht pausenlos hin und her geschichtet werden muss, ist Bucketsort (unter bestimmten Gegebenheiten) ein ausgesprochen flinker Sortieralgorithmus.
Nachteile von Bucketsort:
Die nähere Beschäftigung mit Bucket Sort bringt eine ganze Reihe von Nachteilen ans Tageslicht. So ist zum Beispiel die Dimensionierung des Bucket-Feldes von der Vielfalt der Werte im Primärfeld abhängig. Treten viele verschiedene Werte auf, so muss ein großes Bucket-Feld dimensioniert werden, obwohl dieses u.U. nur zu einem Bruchteil ausgelastet wird. Bucketsort wird sich also nur dort wirklich anbieten, wo die Wertevielfalt relativ gering ist.
Legt man das Bucket-Feld als statisches Array an, so wird man häufig eine enorme Speicherplatzverschwendung in Kauf nehmen müssen. Jedes einzelne Bucket müsste im ungünstigsten Falle das gesamte Primärfeld aufnehmen können, wohingegen alle anderen Buckets leer blieben. Wenn man es mit Bucketsort wirklich ernst meint, kommt man an dynamischen Feldern nicht vorbei.
Ein dritter Aspekt sei genannt. Während die Behandlung eines Integer-Feldes mit wenigen Programmzeilen erledigt ist, muss man bei Real-Zahlen oder gar Strings schon deutlich mehr Aufwand betreiben. Summa summarum lässt es Bucketsort auch an der nötigen Universalität fehlen.
Bucketsort: 2. Variante
Erhöhen wir nun den Schwierigkeitsgrad ein bisschen und versuchen uns an einem Array aus zufällig erzeugten Real-Zahlen zwischen 0 und 100.
Im Applikationsfenster ist das Prinzip dargestellt. Der Wertebereich ist in 10 gleichgroße Intervalle (analog Buckets) aufgeteilt. Jede Zahl wird an einem Kriterium (Schlüssel) gemessen, welches das richtige Bucket zuordnet. Ist dieses gefunden, wird die Zahl innerhalb des Buckets gleich noch mit Insertionsort einsortiert. Das anschließende Zurückschreiben in das Ausgangsfeld ist nun ein Kinderspiel.

Wir vereinbaren für die Buckets einen eigenen Typ (TBucket), der einerseits die Feldelemente aufnehmen kann und andererseits die Anzahl der im jeweiligen Bucket abgelegten Elemente erfasst.

  
const size = 19;

type
  TBucket = record
    anzahl: byte;
    element: array[0..size] of double;
  end;

var
  Form1: TForm1;
  zahl: array[0..size] of double;
  bucket: array[0..9] of TBucket;
  lst: array[0..9] of TComponent;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
var i, j: byte;
begin
  for i:=0 to 9 do lst[i]:=FindComponent('lst'+IntToStr(i));
  // Zufallszahlen erzeugen und darstellen
  randomize;
  for j:=0 to size do
  begin
    zahl[j]:=RoundTo(random(100000)/1000,-3);
    lstUnsort.Items.Add(FloatToStr(zahl[j]));
  end;
  // Bucket-Feld initialisieren
  for i:=0 to 9 do
  begin
    bucket[i].anzahl:=0;
    for j:=0 to size do bucket[i].element[j]:=0;
  end;
end;

procedure TForm1.btnOKClick(Sender: TObject);
var i, j, nr: byte;
begin
  for nr:=0 to size do
  begin
    // Intervall (Bucket) ermitteln
    i:=trunc(zahl[nr]) div 10;
    // Zahl im Bucket einsortieren
    j:=bucket[i].anzahl;
    while (bucket[i].element[j-1]>zahl[nr]) and (j>0) do
    begin
      bucket[i].element[j]:=bucket[i].element[j-1];
      dec(j);
    end;
    inc(bucket[i].anzahl);
    bucket[i].element[j]:=zahl[nr];
  end;
  // Sortiertes Feld zurückschreiben und darstellen
  nr:=0;
  for i:=0 to 9 do
  begin
    if bucket[i].anzahl>0 then
    for j:=0 to bucket[i].anzahl-1 do
    begin
      TListBox(lst[i]).Items.Add(FloatToStr(bucket[i].element[j]));
      zahl[nr]:=bucket[i].element[j];
      lstSort.Items.Add(FloatToStr(zahl[nr]));
      inc(nr);
    end;
  end;
end;