Michael Neuhold Homepage
Startseite > Informatikunterricht > Einfache Sortieralgorithmen

Einfache Sortieralgorithmen

Einfache Sortier- und Suchalgorithmen sollen Schülern einen ersten Einblick in das Thema Algorithmen und Datenstrukturen geben. Komplexere Algorithmen wie Quicksort müssen dabei außen vor bleiben. Was ich selber kaum verstehe, kann ich auch meinen Eleven nicht beibringen.

Die folgenden Pascal-Prozeduren sind im oder für den Unterricht entstanden. Sie sind nicht als Musterbeispiele für guten Programmcode zu verstehen, und sie sind auch nicht besonders generisch gehalten (ich habe mit den Schülern immer nur Integer-Zahlen aufsteigend sortiert). Vielmehr soll der Programmcode die Arbeitsweise der Algorithmen demonstrieren.

Vorüberlegungen

Wesentliche Eigenschaften von Sortieralgorithem sind:

Laufzeitverhalten im Idealfall, im Durchschnitt und im worst case abhängig von einer Datenmenge n.
Stabilität: Ein Sortierverfahren wird stabil genannt, wenn sich die relative Position von Datensätzen mit gleichen Schlüsseln durch die Sortierung nicht ändert. Wenn z.B. ein nach Geburtsdatum sortierter Datenbestand von Personendaten nach Nachnamen sortiert wird, bleiben bei stabilen Verfahren Datensätze mit gleichem Nachnamen weiterhin nach Geburtsdatum sortiert. (Die hier besprochenen einfachen Verfahren sind alle stabil.)
Wie oft Datensätze während des Sortierens bewegt werden müssen. Bei Datenbeständen mit großen Datensätzen und kleinen Schlüsseln wird man aber nicht die Datensätze selber, sondern nur einen Index sortieren.
Ob das Sortieren direkt in den Daten selbst (in-place) erfolgen kann oder ob eine Kopie der zu sortierenden Daten benötigt wird.

Vorbereitung

Mehrere Sortieralgorithmen benötigen eine Prozedur zum Vertauschen von Arrayelementen. Die wollen wir vorab zur Verfügung stellen:

procedure swap (var x,y: integer);
var  mem:integer;
begin
  mem:=x; x:=y; y:=mem;
end;

Für die Praxis, wo u.U. Millionen von Datensätzen sortiert werden müssen, ist so eine Kapselung nicht unproblematisch, weil durch den millionenfachen Funktionsaufruf ein nicht unerheblicher Overhead entsteht. Da sollte man also erwägen, die Tauschroutine direkt in den Sortiercode zu schreiben, wenn der Compiler diese Optimierung nicht automatisch durchführt.

Für die folgenden Prozedurbeispiele nehmen wir an, daß sich die zu sortierenden Integer-Zahlen in einem Array namens zahlen befinden und daß das Array n Elemente enthält.

Bubble Sort und Varianten

Bubble Sort ist ein ineffizienter, aber kurzer Algorithmus: wir vergleichen aufsteigend jedes Arrayelement mit seinem Nachfolger und - falls notwendig - vertauschen die beiden. Nach dem ersten Durchlauf muß zumindest das letzte Element bereits am richtigen Platz sein. Der nächste Durchlauf muß also nur noch bis zur vorletzten Stelle gehen, usw.

procedure bubblesort;
{unsortlen ist die letzte Stelle des noch unsortierten Arrayteiles}
var  unsortlen, i: integer;
begin
  for unsortlen:= (n-1) downto 1 do
    for i:= 1 to unsortlen do
      if zahlen[i] > zahlen [i+1] then
        swap (zahlen[i], zahlen[i+1]);
end;

Die innere Schleife wird n²/2-mal aufgerufen ((n-1) + (n-2) + (n-3) + ... + 1), und zwar unabhängig vom Grad der Sortierung, also auch, wenn die Daten bereits sortiert vorliegen.

Eine Verbesserung von Bubble Sort ist, sich die Stelle des letzten Tausches zu merken. Ab dieser Stelle müssen die Daten ja bereits sortiert sein. Der nächste Durchlauf braucht also nur noch bis zu dieser Arrayposition zu gehen.

procedure enhanced_bubblesort;
var  unsortlen, lastswap, i: integer;
begin
  unsortlen:= n-1; lastswap:=unsortlen;
  while lastswap > 1 do
  begin
    lastswap:=1;
    {innere Schleife des Bubblesort:}
    for i:= 1 to unsortlen do
    begin
      if zahlen[i] > zahlen[i+1] then
      begin
        swap (zahlen[i], zahlen[i+1]);
        lastswap:= i;
      end;
    end;
    {die Verkürzung des noch unsortierten Datenfeldes wird nicht über eine
     äußere FOR-Schleife, sondern über die Zuweisung unsortlen:=lastswap
     gesteuert; lastswap wird bei jedem Tauschvorgang ein neuer Wert zugewiesen; findet
     kein Tauschvorgang mehr statt (weil bereits fertig sortiert), erhält lastswap
     keinen neuen Wert mehr, daher die Zuweisung lastswap:=1 am Beginn der WHILE-Schleife:}
    unsortlen:=lastswap;
  end;
end;

Wenn die Daten bereits sortiert sind, sind wir nach einem Durchlauf fertig. Der Algorithmus hat dann also sogar lineare Laufzeit.

Eine Variante von Bubble Sort ist Shaker Sort: Es wird jeweils ein aufsteigender und ein absteigender Sortierlauf durchgeführt. Das Array wird also von beiden Enden her sortiert. Wenn sich die beiden in der Mitte treffen, sind wir fertig.

procedure shakersort;
var  oben, unten, laenge, anfang: integer;
begin
  unten:=1; oben:=n;
  while oben > unten do
  begin
    {einmal rauf...:}
    for i:= unten to (oben-1) do
    begin
      if zahlen[i] > zahlen [i+1] then
        swap (zahlen[i], zahlen[i+1]);
    end;
    dec (oben);
    {... und einmal runter:}
    for i:= (oben-1) downto unten do
    begin
      if zahlen[i+1] < zahlen[i] then
        swap (zahlen[i+1], zahlen[i]);
    end;
    inc (unten);
  end;
end;

Und natürlich läßt sich hier dieselbe Verbesserung wie beim Bubble Sort vornehmen: Stelle des letzten Tausches merken.

procedure enhanced_shakersort;
var  oben, unten,
     letztoben, letztunten,
     i: integer;
begin
  unten:=1; oben:=n;
  while oben > unten do
  begin
    letztoben:=unten; letztunten:=n;
    for i:= unten to (oben-1) do
    begin
      if zahlen[i] > zahlen [i+1] then
      begin
        swap (zahlen[i], zahlen[i+1]);
        letztoben:=i;
      end;
    end;
    oben:=letztoben;
    for i:= (oben-1) downto unten do
    begin
      if zahlen[i+1] < zahlen[i] then
      begin
        swap (zahlen[i+1], zahlen[i]);
        letztunten:=i;
      end;
    end;
    unten:=letztunten;
  end;
end;

Bubble Sort und seine Abkömmlinge sind aufgrund ihres miserablen Laufzeitverhaltens unbrauchbar für die Sortierung größerer Datenmengen. Aber weil sie so simpel sind, eignen sie sich gut als Spielwiese für das Training algorithmischen Denkens.

Selection Sort (Auswahlsort)

Wir suchen das größte Element und stellen es an die letzte Stelle im Array. Dann das zweitgrößte an die zweitletzte Stelle usw. Anders gesagt: die nächste Einfügestelle steht fest: die letzte Stelle im noch unsortierten Teil des Arrays; es muß das noch verbleibende größte Element gesucht und durch Vertauschen an dieser Stelle eingefügt werden. Im Grunde genommen arbeitet Selection Sort ähnlich wie Bubble Sort: pro Durchlauf wird ein Element an seine richtige Stelle gebracht.

procedure auswahlsort;
var  unsortlen, i, maxpos: integer;
{maxpos ist die Stelle mit dem größten Element im unsortierten Arrayteil}
begin
  for unsortlen:= n downto 2 do
  begin
    {größtes Element suchen und Stelle merken:}
    maxpos:=1;
    for i:= 2 to unsortlen do
    begin
      if zahlen[i] > zahlen[maxpos] then
        maxpos:=i;
    end;
    {wenn das größte Element nicht schon an der richtigen Stelle:}
    if maxpos <> unsortlen then
      swap (zahlen[maxpos], zahlen[unsortlen]);
  end;
end;

Selection Sort hat bei unsortierten und vorsortierten Daten gleich lange Laufzeiten, es benötigt etwa n²/2 Vergleiche. Eine wesentliche Eigenschaft dieses Algorithmus ist, daß jedes Element nur einmal bewegt wird, es werden also max. n Austauschoperationen (=Aufrufe von swap) benötigt.

Insertion Sort (Einfügesort)

Der Insertion Sort ahmt die Vorgehensweise beim Sortieren von Karten beim Kartenspielen nach: wir betrachten aufsteigend jedes Element und lassen es soweit nach unten rücken (d.h. wir vergleichen es mit seinem Vorgänger und, falls nötig, vertauschen wir die beiden), bis es am richtigen Platz steht. Anders gesagt: das nächste einzufügende Element steht fest, es muß die passende Einfügestelle im bereits sortierten Teil des Arrays gefunden werden; dabei werden die Elemente solange hinaufgerückt, bis die passende Einfügestelle erreicht ist.

procedure einfuegesort;
var  elem, pos, i:integer;
begin
  for pos:=2 to n do
  begin
    {merke Stelle in einer Zählvariablen, merke Element dieser Stelle:}
    i:=pos; elem:= zahlen[pos];
    {solange dieses Element kleiner als sein Vorgänger und Stelle größer 1:}
    while (elem < zahlen[i-1]) and (i <> 1) do
    begin
      {der aktuellen Stelle den Inhalt des Vorgängers zuweisen, Zählvariable dekrementieren:}
      zahlen[i]:= zahlen[i-1];
      i:=i-1;
    end;
    zahlen[i]:=elem;
  end;
end;

Dieser Algorithmus ist wie der verbesserte Bubble Sort bei sortierten Daten nach einem Durchlauf fertig und hat somit lineare Laufzeit. Der worst case sind umgekehrt sortierte Daten: in diesem Fall sind laut Robert Sedgwick n²/2 Vergleiche und n²/4 Austauschoperationen notwendig.

Eine etwas komplizierte Variante von Insertion Sort ist Shellsort. Es basiert auf der Überlegung, die Daten so umzuordnen, daß man, wenn man nur jedes h-te Element betrachtet, eine sortierte Teildatei erhält. Wir vergleichen also Elemente nicht mit unmittelbaren Nachbarn, sondern mit um h entfernten Elementen. Wenn man diese h-Sortierung für immer kleinere h durchführt, erhält man schließlich eine sortierte Datei. Die Schwierigkeit besteht darin, geeignete h zu finden.

Dieses Verfahren ist für den Unterricht allerdings zu komplex. Daher habe ich es selber noch nie implementiert.

Autor: Michael Neuhold (E-Mail-Kontakt)
Letzte Aktualisierung: 24. März 2017