Sortier­algorithmen

1. Einleitung
2. Einteilung
   1. Laufzeit
   2. Stabilität
   3. Stationär vs. nonstationär
   4. Intern vs. extern
   5. Speicherbedarf
   6. Rekursion vs. Iteration
3. Elementare Sortier­algo­rithmen
   1. Bubble Sort
   2. Shake Sort
   3. Insert Sort
   4. Select Sort
4. Höhere Sortier­algo­rithmen
   1. Quick Sort
5. Literatur

Einleitung

Laut einer Statistik beschäftigen sich Großrechner ein Viertel ihrer Zeit nur mit Suchen und Sortieren. Beides ist oft mit langen Laufzeiten verbunden: Grund genug also, daß wir einen Blick darauf werfen, wie man es schneller machen kann.

Bequemes Erfassen von Daten für Benutzer. Als Beispiel die Befehle zum Anzeigen der Dateien des aktuellen Verzeichnisses sortiert nach Datum/Uhrzeit:

UNIX: ls -sort=time
DOS: dir/od

Als zweites Beispiel die sortierte Anzeige einer Postleitzahldatei:

UNIX: cat plz.txt | sort
DOS: type plz.txt | sort, oder einfach nur: sort < plz.txt

Voraussetzung für andere Algo­rithmen. Viele Algo­rithmen setzen bei der Verarbeitung von Daten voraus, daß diese schon sortiert vorliegen. Die sehr schnelle binäre Suche z.B. liefert nur für vorsortierte Daten korrekte Ergebnisse!

Einteilung

Einige Algo­rithmen sind für alle möglichen Daten geeignet, andere nur in speziellen Situationen sinnvoll.

Laufzeit

Die einfachste und vielleicht gebräuchlichste Einteilung von Sortier­algo­rithmen ist die nach der benötigten Zeit t bzw. Komplexität Θ. Einfache Verfahren haben meist eine Laufzeit, die zum Quadrat der Anzahl n der zu sortierenden Elemente proportional ist, während höhere meist eine Laufzeit proportional zu n log n aufweisen.

Stabilität

Eine weitere sehr wichtige Eigenschaft von Sortier­algo­rithmen ist die Stabilität. Als instabile Sortier­verfahren bezeichnet man solche, die die relative Reihenfolge gleicher Elemente nicht erhalten: wird z.B. eine alphabetisch sortierte Kundendatei nach den Postleitzahlen sortiert, werden danach die Kunden einer Postleitzahl nicht mehr alphabetisch sortiert, sondern ungeordnet vorliegen.

Es ist immer wieder erstaunlich, wie selbstverständlich Programmierer Stabilität annehmen: zwar sind die meisten elementaren Sortier­verfahren stabil, die meisten höheren jedoch nicht!

Stationär vs. non-stationär

Stationäre Verfahren haben die Eigenschaft, sich beim Sortieren immer nur auf ein kleines Datenfeld zu konzentrieren (z.B. Quick Sort), während nicht-stationäre schnell wandern oder sogar ständig über das ganze Feld springen (analog zu einem „full stroke“ bei Festplattenzugriffen). Erstere profitieren sehr deutlich von zwischengeschalteten systemischen Cache-Mechanismen, die Laufzeit kann beträchtlich sinken.

Extern vs. intern

Beim Zugriff auf externe Daten wie Bänder etc. sind neben den algo­rithmischen auch systemische Kriterien zu beachten: die Zugriffszeiten auf die zu sortierenden Daten sind oft Hunderte Male größer und zumeist kann nur sequentiell auf die Daten zugegriffen werden.

Speicherbedarf

Je nach Speicherbedarf des Algo­rithmus unterscheidet man:

1. Lokale Verfahren, die mit keinen oder nur wenigen Hilfsvariablen auskommen.
2. Verfahren, die pro zu sortierendes Element wenigstens eine Variable benötigen.
   Bsp: eine verkettete Liste, wobei jedes Listenelement auf ein Feldelement zeigt. Zum Sortieren braucht man nur die Reihenfolge der Listenelemente zu ändern, nicht aber das Originalfeld. Logische Views und Indexdateien arbeiten nach diesem Schema, das immer dann zu empfehlen ist, wenn Daten häufig umsortiert werden sollen.
3. Verfahren, die zum Sortieren das ganze zu sortierende Feld als Kopie vorhalten müssen.

Rekursion vs. Iteration

So man will, kann man Algo­rithmen, und damit auch die zur Sortierung verwendeten, in rekursive und iterative Varianten unterscheiden. Es läßt sich prinzipiell jede Rekursion über drei Stacks in eine nichtrekursive Form umwandeln.

Über das Pro und Contra von Rekursionen sind Dutzende von Büchern geschrieben worden. In den 70er Jahren wurde die Rekursion verteufelt, um in den 80ern eine Renaissance zu feiern. Fakt ist, daß beide Methoden ihre Vor- und Nachteile haben.

Der unumstrittene Vorteil der Rekursion liegt darin, bestimmte Probleme, die von Natur aus rekursiv sind, sehr kurz und elegant beschreiben zu können (Turm von Hanoi, Quick Sort, alle fraktalen Strukturen).

Der Nachteil liegt im erhöhten Speicherbedarf für den Stack, der bei vielen Rekursionszyklen zum Programmabsturz führen kann. Die Compiler bzw. Interpreter mancher Programmier­sprachen (z.B. LISP, PROLOG) können allerdings rekursiv vom Programmierer definierte Funktionen durch eine sog. Tail Recursion Optimisation (TRO) intern entrekursivieren. Voraussetzung dafür ist jedoch, daß der Wiederaufruf der Funktion am Ende der Funktion definiert ist, so daß beim Rücklauf durch den Stack keine Variablen mehr für die einzelnen Zyklen vorgehalten werden müssen. Dies geht nicht bei allen Rekursionen: bei der Folge des Fibonacchi erfolgt nach dem Aufruf der einen Rekursion gleich noch ein zweiter Aufruf, eine TRO ist so nicht möglich.

Ein weiterer Nachteil ist, daß die mit der Rekursion verbundenen Funktions­aufrufe und Stack­allozierungen auf den meisten Systemen mehr Zeit brauchen als eine Schleife mit Variablen.

Entsprechend umgekehrt präsentieren sich die Vor- und Nachteile einer Iteration: der Stack wird geschont, aber der Quellcode zur Implementierung ist meist sehr schwer zu lesen und dementsprechend zu pflegen – ein Umstand, der nicht leicht wiegt!

Elementare Sortier­algo­rithmen

Bubble Sort

Einführung

Ein sehr bekannter Algo­rithmus mit schlechter Performanz, aber einfach zu verstehen für Anfänger. Wohl daher das in Anfängerkursen zumeist vorgestellte Verfahren. Er ist stabil.

Grundprinzip

In einer Schleife wird jedes Element eines Feldes mit seinem nachfolgendem Nachbarn verglichen. Ist der Nachbar kleiner, werden beide ausgetauscht. Dies wiederholt sich n-1 mal mit n = Elementanzahl des Feldes. Bei jedem Durchgang wandert damit das größte Element nach hinten wie eine Luftblase im Wasser, daher auch der Name.

Implementierungen

Naiver Algo­rithmus

Die Komplexität beträgt durch die gekoppelte FOR-Schleife Θ(n) = n².

typedef
  unsigned int titem;


void srtbub01(titem a[], size_t len)
  {
  int i, j;
  titem h;

  for (j=1; j<len; j++)
    for (i=0; i<len-1; i++)
      if (a[i] > a[i+1]) {
        h = a[i];
        a[i] = a[i+1];
        a[i+1] = h;
        }
  }

type
  titem = word;
  ta = array[0..99] of titem;

procedure srtbub01(var a:ta; len:word);
  var
    i, j : integer;
    h : titem;
  begin
  for j:=1 to len-1 do
    for i:=0 to len-2 do
      if a[i] > a[i+1] then begin
        h := a[i];
        a[i] := a[i+1];
        a[i+1] := h
        end
  end;

Optimierter Algo­rithmus

Da in jedem Durchgang das jeweils größte Element schon hinten angekommen ist und somit das Feld hinten also schon sortiert ist, braucht man nicht jedesmal bis zum bitteren Ende des Feldes vergleichen, sondern nur bis zum vorletzten Element des letzten Durchgangs. Zudem wird ein Vergleich mit 0 in der Regel vom Prozessor (compiler- und maschinen­abhängig) schneller abgearbeitet. Die Komplexität beträgt Θ(n) = n²/2, d.h. halbierte Laufzeiten im Vgl. zum naiven Ansatz.

void srtbub02(titem a[], size_t len)
  {
  int i, j;
  titem h;

  for (j=len-2; j>=0; j--)
    for (i=0; i<=j; i++)
      if (a[i] > a[i+1]) {
        h = a[i];
        a[i] = a[i+1];
        a[i+1] = h;
        }
  }

Shake Sort

Noch fehlend…

Insertion Sort

Einführung

Der Insertion Sort ist ein Sortier­verfahren, daß sich vor allem für vorsortierte Daten eignet; in diesem Fall arbeitet er auch schneller als der Bubble Sort. Die Komplexität beträgt wie auch beim Bubble Sort durch die gekoppelte Schleife Θ(n) = n². Er ist stabil.

Grundprinzip

Der Insertion Sort arbeitet ähnlich einem Karten­spieler, indem er durch die Elemente wandert und jedes Element vorne der Größe nach einfügt. Er ist damit nicht stationär.

Implementierungen

Noch fehlend…

Select Sort

Da jedes Element nur einmal bewegt wird, ist der Select Sort ein günstiges Verfahren zum Sortieren von Daten mit kleinen Schlüsseln und großen Datensätzen als auch von externen Daten. Er ist stabil.

Grundprinzip

Der Name des Select Sort rührt von der Methode, das jeweilige Minimum bei jedem Feldlauf direkt auszuwählen und vorne entsprechend einzusortieren (via Austausch). Zwar ist die Zahl der Vergleiche mit Θ(n) = n² so hoch wie beim Bubble und Insertion Sort, aber durch die reduzierte Zahl der Bewegungen infolge des Austausches (statt Einsortieren wie beim Insertion Sort) mit Θ(n) = n log n beiden deutlich überlegen – sofern die Daten nicht schon vorsortiert sind.

Implementierungen

Noch fehlend…

Höhere Sortier­algo­rithmen

Quick Sort

Einführung

Der schnellste und bekannteste höhere Standard-Sortier­algo­rithmus für Felder ist der 1962 von C.A.R. Hoare im Computer Journal, 5 publizierte Quick Sort, der von Donald E. Knuth auch Partitions-Austausch-Sort genannt wird. Er ist instabil und stationär.

Er ist sehr beliebt, da seine Implementierung sehr einfach und elegant ist (zumindestens in der rekursiven Version). Er ist ein gutes Mehrzweck-Sortier­verfahren und erfordert in den meisten Situationen weniger Ressourcen als andere Sortier­verfahren, so daß er sogar fester Bestandteil der Sprache C und C++ und damit auch von UNIX geworden ist.

Viele haben sich seitdem an einer „Optimierung“ des Kernes von Quick Sort versucht und sind gescheitert: Der Algo­rithmus von Hoare ist schon so ausgewogen, daß Verbesserungen in einem Programmteil durch Leistungs­einbußen in anderen Programm­teilen mehr als zunichte gemacht werden. Die wenigen Ausnahmen von dieser Regel sind weiter unten beschrieben.

Quick Sort ist der wahrscheinlich bestuntersuchte Sortier­algo­rithmus überhaupt: er war Gegenstand mehrerer gründlicher mathema­tischer Unter­suchungen (Sedgewick dissertierte 1975 an der Stanford University über Quick Sort), und empirische gewonnene Daten stützen die Annahmen dieser Untersuchungen.

Gegenüber den elementaren Sortier­verfahren wie Bubble Sort, Insertion Sort oder Select Sort weist der Quick Sort als höherer Sortier­algo­rithmus eine deutlich geringere Laufzeitkomplexität auf. Benötigen erstere Laufzeiten, die im Quadrat zur Anzahl der zu sortierenden Elemente steigen (Θ(n) = n²), benötigt der Quick Sort nur durchschnittlich Θ(n) = n log n.

Der Nachteil von Quick Sort liegt in dem Fall, daß man keine schon annähernd vorsortierte Daten mit Quick Sort sortieren sollte: erstens steigt die Laufzeit des sog. „entarteten“ Sorts zum Quadrat der Elementzahl n an (ein entarteter Quick Sort weist also die Komplexität eines Bubble Sorts auf), was noch nicht so schlimm ist – für solche Daten bietet sich grundsätzlich ein anderes Sortier­verfahren, hauptsächlich der Insertion Sort, an – aber zweitens steigt der Stapel­speicher­bedarf der rekursiven Quick-Sort-Variante stark an: im schlimmsten Fall werden n Einträge Stapel­speicher benötigt, was zum Absturz des Programms führen kann. Diesen Nachteil kann man umgehen, indem man den Algo­rithmus ent­rekursi­viert und eine End­rekursions­optimierung (TRO) durchführt, was zu einem Speicherbedarf von maximal lg n Stapel­einträgen führt. Allerdings ist die nonrekursive Version des Algo­rithmus unübersichtlicher und schwieriger zu lesen. Allerdings hat man nicht immer die Wahl: Programmiersprachen, die keine Rekursion erlauben, wie z.B. ältere Fortran-Dialekte sind auf nonrekursive Implementierungen angewiesen.

Grundprinzip

Beim Quick Sort kommt eine Strategie zum Einsatz, die man als „Divide et Impera“ umschreiben kann:

Zuerst wird ein willkürliches Trennelement aus den zu sortierenden Elementen ausgewählt, häufig das mittlere. Im Idealfall entspricht das Trennelement dem Median der zu sortierenden Zahlenfolge, d.h. die Hälfte der Elemente ist kleiner, die andere größer als das Trennelement.

Danach wird das Feld so umgeordnet, daß sich links vom Trenn­element nur noch kleinere, rechts nur noch größere Elemente befinden. Dieser Austausch läßt sich in einem Durchgang mit zwei sich aufeinanderzu­bewegenden Indices leicht erreichen.

Die entstandene Teilsortierung (Partitio­nierung) hat zwei Teilfelder derart entstehen lassen, daß alle Elemente des unteren Teilfeldes kleiner sind als alle Elemente des oberen. Ein Austausch von Elementen zwischen beiden Teilfeldern ist nun nicht mehr nötig, beide Teilfelder können nun separat sortiert werden.

Also wendet man die Umordnung nacheinander (oder parallel bei multithreading-fähigen Betriebs­systemen) auf beide Teilfelder erneut an. Dadurch entsteht ein in natürlicher Weise rekursiver Algo­rithmus, der in immer mehr Instanzen zerfällt, die auf immer kleineren Teilfeldern operieren.

Die Rekursion wird abgebrochen, falls die durch die Partitionierung entstandenen Teilfelder auf die Länge von 1 geschrumpft sind (ein Teilfeld mit nur einem Element ist immer sortiert).

Implementierungen

Bei den nachfolgenden Routinen sei a das zu sortierende Array, l die linke und r die rechte Grenze des zu sortierenden Bereichs. Bei manchen Versionen wird ein Sentinel am Anfang oder Ende benötigt, damit die Schleifen nicht über das Feld hinauslaufen. Dies passiert, um schleifen­interne zeitraubende Abfragen zu vermeiden (Loop strength reduction).

Rekursiver Algo­rithmus

/* Precondition: MIN Sentinel in a[l] */
void srtqck01(titem a[], int l, int r)
  {
  int i, j;
  titem v, h;

  if (r <= l)
    return;

  i = l - 1; j = r; v = a[r];
  do {
    do i++; while (a[i] < v);
    do j--; while (a[j] > v);
    h = a[i]; a[i] = a[j]; a[j] = h;  /* [1] Exchange */
    } while (i < j);
  a[j] = a[i]; a[i] = v; a[r] = h;  /* [2] Undo last [1] and move v */
  srtqck01(a,l,i-1);
  srtqck01(a,i+1,r);
  }

Optimierter Algo­rithmus 1

Nachfolgender A. arbeitet mit einem expliziten Stack als ADT, um der Rekursion und damit dem gefürchteten Stack Overflow zu entgehen. Häufig ist dies mit einer Leistungssteigerung verbunden: Funktionsaufrufe der rekursiven Variante kosten (maschinenabhängig) Zeit.

void srtqck02(titem a[], size_t len)
  {
  int i, j, l, r;
  titem v, h;

  if (len < 2)
    return;

  PUSH(0); PUSH(len-1);
  do {
  POP(r); POP(l);
    do {
      i = l; j = r; v = a[(l+r)/2];
      do {
        while (a[i] < v) i++;
        while (a[j] > v) j--;
        if (i <= j) {
          h = a[i]; a[i] = a[j]; a[j] = h;
          i++; j--;
          }
        } while (i <= j);
      if (i < r) {
        PUSH(i); PUSH(r); }
      r = j;
      } while (l < r);
    } while(!ISEMPTY);
  }

Optimierter Algo­rithmus 2

Hier wird zusätzlich über das Makro SRT3 (Sortierung dreier Zahlen) die Median-of-three-Technik angewandt, um evtl. Entartungen zu entgehen. Insbesondere bei schon leicht vorsortierten Daten wird der Algo­rithmus deutlich schneller!

static void srtqck03(titem a[], size_t len)
  {
  int i, j, l, r;
  titem v, h;

  if (len < 2)
    return;

  PUSH(0); PUSH(len-1);
  do {
  POP(r); POP(l);
    do {
      i = (l + r) / 2;
      SRT3(a[l],a[i],a[r],h);
      v = a[i];
      i = l + 1; j = r - 1;
      do {
        while (a[i] < v) i++;
        while (a[j] > v) j--;
        if (i <= j) {
          h = a[i]; a[i] = a[j]; a[j] = h;
          i++; j--;
          }
        } while (i <= j);
      if (i < r) {
        PUSH(i); PUSH(r); }
      r = j;
      } while (l < r);
    } while(!ISEMPTY);
  }

Optimierter Algo­rithmus 3

Durch den vorzeitigen Abbruch des Quick Sorts ab einer gewissen Teilfeld­größe STOP und Nach­behandlung des nun fast sortierten Feldes mit einem elementaren Sort, vorzugsweise dem Insertion Sort, kann die Geschwindig­keit noch einmal gesteigert werden. Vorsicht aber: ist der Quick Sort fehlerhaft implementiert, bekommt der Insertion Sort ein völlig unsortiertes Feld zur Bearbeitung. Der einzige Indikator, daß dann etwas nicht stimmt, sind die extremen Laufzeiten!

Implementiert man alle drei genannten Optimierungen aber fehlerfrei, kann Quick Sort um bis zu 30% beschleunigt werden. Diese Variante ist (maschinen- und compilerabhängig) bis zu 100% schneller als die C-eigene Bibliotheks­funktion qsort().

#define STOP 5

static void srtqck04(titem a[], size_t len)
  {
  int i, j, l, r;
  titem v, h;

  if (len < 2)
    return;

  PUSH(0); PUSH(len-1);
  do {
  POP(r); POP(l);
    do {
      i = (l + r) / 2;
      SRT3(a[l],a[i],a[r],h);
      v = a[i];
      i = l + 1; j = r - 1;
      do {
        while (a[i] < v) i++;
        while (a[j] > v) j--;
        if (i <= j) {
          h = a[i]; a[i] = a[j]; a[j] = h;
          i++; j--;
          }
        } while (i <= j);
      if (i < r) {
        PUSH(i); PUSH(r); }
      r = j;
      } while (l + STOP < r);
    } while(!ISEMPTY);
  }

Bernhard schrieb dazu am 12.09.2010: Hallo. Ich habe ein paar Anmerkungen zu den Sortieralgorithmen (im speziellen Quicksort), da ich mich in letzter Zeit sehr viel mit der Implementierung solcher beschäftigt hatte. Die von der Stdlib implementierte Version des Qsort ist sehrwohl (zumindest in der glibc) mit \"Median-Of-Three\"-Technik und Abbruch bei einer bestimmten Länge (~4) der Teilfolgen implementiert. Der Grund, dafür, dass der von Dir gezeigte Algorithmus schneller als die Standard-C-Funktion qsort ist liegt in erster Linie daran, dass Du die Vergleichsoperation direkt in der Sortierfunktion durchführst und nicht via Callback (Function-Pointer), so wie das beim generischen qsort() gemacht wird. Da die Vergleichsfunktion beim Sortieren sehr oft aufgerufen wird, liegt hier der einzige schwache Punkt von qsort(). Für einen Direktvergleich mit Deiner Implementierung müsstest Du auch die Vergleichsfunktion über einen Callback implementieren. LG Bernhard

Asdala antwortete am 12.09.2010: Hallo Bernhard, vielen Dank für die Klarstellung. Die o.g. Zahlen entstammen einem Vergleich aus dem Jahre 1998 unter Win98 und Turbo-C. Über viele Jahre gereifte Biblio­theken, zu denen man die GLIBC zählen darf, nutzen naturgemäß einschlägige Optimierungen, so daß (abhängig von der verwendeten Bibliothek) der Geschwindigkeits­vorteil der hier vorgestellten Variante tatsächlich nur aus der direkten Kodierung des Werte­vergleiches in der Sortier­routine resultieren kann. In solch einem Falle ist ein Laufzeit­vorteil gegenüber der Bibliothek in der Tat trivial und bedarf keiner weiteren Kommentierung. Kommt es auf jedes Quentchen Geschwindig­keit an, wird man die direkte Kodierung trotz des damit verbundenen erhöhten Pflege­aufwandes bevorzugen und in Fällen, in denen Umfang und Art der zu sortierenden Daten von vornherein bekannt sind, sogar weitere Optimierungen vornehmen, die ein Bibliotheks­algorithmus aufgrund seines universellen Anspruches selbstredend nicht leisten kann. Viele Grüße Asdala

Fazit: Für Anwendungen, die ein Höchstmaß an Schnelligkeit brauchen, oder für Compiler ohne eingebauten Quick Sort sind o.g. Algo­rithmen geeignet. In diesem Fall kann man sogar noch weitere Verbesserungen erzielen, wenn man die innere Schleife komplett in Assembler codiert. Für die Wald- und Wiesen­anwendungen hingegen reichen die Bibliotheks­funktionen der Compiler wie im nachfolgenden Beispiel:

#include <stdlib.h>
#include <string.h>

static int sortfunc(const void *e1, const void *e2)
  {
  return strcmp(*(char**)e1, *(char**)e2);
  }

void srtqck05(char* a[], size_t len)
  {
  qsort((void*)a, len, sizeof a[0], sortfunc);
  }

char *list[] = { "Müller", "Meier", "Schmidt", "Bauer", "Fischer" };

int main(void)
  {
  ..
  srtqck05(list, sizeof list/sizeof list[0]);
  ..
  }

Heap Sort

Shell Sort

Radix Sort

Comb Sort

B Sort

Merge Sort

Literatur

1. Sedgewick R.; Quick Sort; Garland; New York; 1978
2. Sedgewick R.; Algo­rithmen; Addison-Wesley; Bonn; 1997; S. 121 ff.
3. Hermann D.; Algo­rithmen-Arbeitsbuch; Addison-Wesley; München; 1992; S. 296 ff.
4. Knuth D.E.; The Art of Computer Programming. Volume 3: Sorting and Searching; Addison-Wesley; Reading, MA; 1975
5. Hoare C.A.R.; Computer Journal 5, 1; USA; 1962
6. Ruhland J.; TOOL Informatik: Datenstrukturen und elementare Algo­rithmen; Vogel; Würzburg; 1991; S. 16 ff.