Kurs:Algorithmen und Datenstrukturen/Kapitel 2/QuickSort

Quicksort ist ein rekursiver Algorithmus, der eine Gruppe von Datensätzen so sortiert, dass alle Datensätze deren Schlüssel größer sind als ein sogenanntes Pivotelement sich anschliessend in einer Teilgruppe befinden und die, deren Schlüssel größer sind, in einer anderen Teilgruppe. Da das Pivotelement den Grenzwert zwischen den beiden Teilgruppen darstellt, dürfen Datensätze deren Schlüssel gleich dem Pivotelement sind in jeder der Teilgruppen verbleiben, da sich diese Datensätze im weiteren Verlauf der Sortierung an exakt dieser Grenze sammeln werden. Enthält eine Teilgruppe nur noch ein oder kein Element mehr, wird die Rekursion abgebrochen.

Die einfachste Variante zur Bestimmung des Pivotelementes besteht darin, einfach den Schlüssel des ersten oder letzten Datensatzes aus der Gruppe zu nehmen. Je gleichmäßiger die Elemente der Gruppe auf die Teilgruppen aufgeteilt wird, desto schneller arbeitet der Algorithmus. Je nach Wahl des Pivotelementes und einer möglichen Vorsortierung kann der Zeitbedarf über

T = C * n * lg₂(n)

oder über

T = C * n²

abgeschätzt werden. Die Bestimmung des Pivotelementes ausschließlich über das erste oder letzte Element kann sich also als günstig oder ungünstig erweisen.

Eine einfach zu realisierenden Verbesserung ergibt sich, wenn man drei Kandidaten bestimmt und den mittleren davon auswählt. Eine weitere Variante wählt das Pivotelement zufällig aus, wodurch eine durchgängig schlechte Pivotwahl sehr unwahrscheinlich wird. Vom zeitlichen Verhalten her ist es sogar sinnvoll, den Durchschnittswert aller Kandidaten zu bestimmen und dann den Kandidaten auszuwählen, der am dichtesten an dem Durchschnittswert liegt.

Das folgende C-Programm dient der Sortierung eines Array mit der Struktur SortKeys. Der Schlüssel, nach dem sortiert werden soll, ist TheInt. Die Daten könnten etwa in einer Liste mit folgender Struktur abgelegt sein:

struct SortKey
  {
  char   TheChar;                                // zusätzliche Spalte zum Sortieren
  short  TheShint;                               // dito als kurzer Integer
  int    TheInt;                                 // Integer, der auch negativ ist
  float  TheFloat;                               // normale Gleitkommazahl
  double TheDouble;                              // Gleitkommazahl mit doppelter Genauigkeit
  int    ThePos;                                 // Position, wo der Schlüssel steht
  int    TheLength;                              // Länge des Schlüssels
  char   TheKey[MAXWLNG + 1];                    // der Schlüssel selbst
  };

Angenommen, man hätte 1.000.000 Million Datensätze, so würde die Sortierung mittels

QSortInt(0, 999999);

aufgerufen werden.

struct SortKey Sortkeys[1000000];                // Array, dass die Daten enthält


void QSortInt(int Links, int Rechts)
  {
  int Grenze;
  Level++;
  if(Links < Rechts)
    {
    Grenze = IntGrenze(Links, Rechts);
    QSortInt(Links, Grenze - 1);
    QSortInt(Grenze + 1, Rechts);
    };
  Level--;
  }


int IntGrenze(int Links, int Rechts)
  {
  int  I, J, K, Pivot;
  int  Z1, Z2;
  char SaveChar;
  char* FromPoi;
  char* ToPoi;


  I = Links;
  J = Rechts - 1;
  Pivot = Rechts;


  do                       // durch aufrufendes Programm ist sicher gestellt, dass Rechts immer größer als Links ist
    {
    while(I < Rechts)      // von links suchen, bis erstes Element größer als Pivot
      {
      Z1 = SortKeys[I].TheInt;
      Z2 = SortKeys[Pivot].TheInt;
      if(Z1 > Z2) break;
      I++;
      };


    while(J > Links)      // von Rechts suchen, bis erstes Element kleiner als Pivot
      {
      Z1 = SortKeys[J].TheInt;
      Z2 = SortKeys[Pivot].TheInt;
      if(Z1 < Z2) break;
      J--;
      };


    if(I < J)              // falls je ein Element kleiner und größer als der Pivot gefunden wurde, diese tauschen
      {
      FromPoi = (char*) &SortKeys[I];
      ToPoi   = (char*) &SortKeys[J];
      for(K = 0; K < KeyLng; K++)
        {
        SaveChar   = ToPoi[K];
        ToPoi[K]   = FromPoi[K];
        FromPoi[K] = SaveChar;
        };
      };
    } while(I < J);


  if(SortKeys[I].TheInt > SortKeys[Pivot].TheInt)
    {
    FromPoi = (char*) &SortKeys[I];
    ToPoi   = (char*) &SortKeys[Pivot];
    for(K = 0; K < KeyLng; K++)
      {
      SaveChar   = ToPoi[K];
      ToPoi[K]   = FromPoi[K];
      FromPoi[K] = SaveChar;
      };
    };


  return(I);
  };