Zur Visualisierung der Arbeitsweise einiger Sortierverfahren sei auf folgendes Applet verwiesen: http://www.inf.hs-anhalt.de/~Worzyk/IiN/applets/sortierverfahren/applet.html

Ein sehr anschaulicher Vergleich der Geschwindigkeit von Sortierverfahren findet sich hier: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm

Insertion Sort

Idee: Einfügen jeweils eines Elementes in eine bereits sortierte Liste. Der Platz für neues Element wird gesucht, das Element wird eingefügt, größere Elemente müssen um jeweils einen Platz verschoben werden. Lohnt sich vor allem bei vorsortierten Abfolgen.

Wikipedia: http://de.wikipedia.org/wiki/Insertion_sort

Bubble Sort

Es werden jeweils zwei benachbarte Elemente verglichen und - abhängig von der Vergleichsoperation - vertauscht. Damit gelangt im ersten Durchgang das kleinste Element an den Anfang der Datenstruktur (bzw. - je nach Programmierung - das größte ans Ende). Im nächsten Durchgang werden dann wieder zwei benachbarte Elemente verglichen, wobei dann das zweitkleinste an die zweite Stelle gelangt usw. Vorteil: Geringster Aufwand bei fast sortierten Folgen Nachteil: Eines der ineffizientesten Sortierverfahren überhaupt.

Wikipedia: http://de.wikipedia.org/wiki/Bubble_Sort

Merge Sort

Idee: Basiert auf dem Prinzip "Divide and Conquer (Teile und beherrsche)" und der Beobachtung, dass sich ein Problem u.U. in zwei Teilprobleme zerlegen lässt, die insgesamt einfacher zu lösen sind.

Wikipedia: http://de.wikipedia.org/wiki/Mergesort

 

Quicksort

Idee:

Grob vorsortieren und in geeignet gewählten Teilbereichen dann feinsortieren, durch erneutes Grobsortieren und erneutes Bilden von Teilbereichen.

Man sortiert ein Array bzw. ein Teilintervall eines Arrays, indem man zunächst vorsortiert: man schafft größere Werte nach rechts und kleinere Werte nach links, dergestalt, daß im Gesamtintervall I i.w. in ein linkes Teilintervall I1 mit kleineren Werten und ein rechtes Teilintervall I2 mit größeren Werten entsteht.

Wikipedia: http://de.wikipedia.org/wiki/Quicksort

Die beiden Teilintervalle I1 und I2 nennt man eine Zerlegung des Ausgangsintervalls. Das ganze Ausgangsintervall I sortiert man, indem man im Vorsortierschritt die Teilintervalle I1 und I2 bildet und dann dasselbe Verfahren auf beide Teilintervalle anwendet. Das läßt sich am einfachsten rekursiv formulieren.

Die Rekursion löst man dann meistens mittels eines Stacks in eine iterative Formulierung auf. Damit ist die behandelbare Problemgröße nicht mehr von der festen Größe des Stacks des Laufzeitsystems abhängig, und man sollte auch wegen des Wegfalls der vielen rekursiven Aufrufe Laufzeit sparen.

Details:

Man wird Werte paarweise tauschen, d.h. einen größeren Wert links gegen einen kleineren Wert rechts tauschen.

Dazu wird man von "außen nach innen", d.h. von links nach rechts und von rechts nach links Paare a[left] und a[right] miteinander vergleichen.

Eine schlechte Idee wäre, a[left] > a[right] zum Austauschkriterium zu machen, siehe folgendes Beispiel:

Man müßte später den Wert 18, der ganz hinten gelandet ist, wieder nach vorne schaffen!

Am besten müssen wohl alle "kleineren" Werte nach vorne getauscht werden und alle "größeren" nach hinten. Dazu wäre es am günstigsten, wenn man den mittleren Wert (Median) aller Arraywerte über dem Intervall I ermitteln könnte und ihn als Vergleichswert zum Paartausch benutzen würde. Sei also aMed der Median der Werte des Ararys a. Dann vertausch man ein Wertepaar a[left] und a[right], wenn a[left] >= aMed && a[right] <= aMed.

Im folgenden Beispiel ist 23 der mittlere Wert aMed. Nach zwei Paarvertauschungen dient das Suchen nach einem weiteren Paar lediglich noch der Ausweitung der Intervalle I1 und/oder I2.

Tatsächlich wird man den Median nicht berechnen, weil das viel zu aufwändig wäre, es würde seinerseits ein Sortieren erfordern. Einfache Implementationen des Quick Sort nehmen schlicht einen beliebigen Wert aus dem Intervall der zu sortierenden Werte als Vergleichswert im Austauschkriterium. Das kann zu einem schlechteren Vorsortieren führen und zu einer schlechten Leistung (Entartung) des Quick Sort. Wir gehen hier nicht darauf ein, wie man dem begegen kann, sonder führen nur die Grundidee weiter aus.

Ausformulierung des Vorsortierens

Man reduziere das abzuarbeitende Intervall [left, right] in einer Schleife, bis es leer ist (left > right). In jedem Schleifenschritt wähle man einen Vergleichswert acrit (a wie a[], crit wie critical oder criterion) aus dem Bereich der Arraywerte des vorzusortierenden Intervalls, d.h. man wähle ein k0 aus [left, right] und setze acrit = a[k0]. In jedem Schleifenschritt suche man sukzessive von links durch Erhöhen von left nach einem Austauschkandidaten mit a[left] >= acrit Ebenso suche man sukzessive von rechts durch Erniedrigen von right nach einem Austauschkandidaten mit a[right] <= acrit. Wenn left <= right gilt, hat man ein Austauschpaar gefunden. In diesem Fall tausche man aus und erhöhe left bzw. erniedrige right, um das Suchintervall auf den verbleibenden Rest zu verkleinern.

void function partialsort( int[] a, long left0, long right0) { // führt einen
    // Vorsortier-/Zerlegungsschritt aus.
    int acrit, temp;
    long left, right;
    left = left0; right = right0;
    "wähle den Vergleichswert acrit als ein a[k0] mit einem k0 aus [left, right]"

    do {
        while (a[left]  < acrit) left++;
        while (a[right] > acrit) right--;
        if ( left <= right ) { // Paartausch
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            left++; right--;
        }
    } while ( left <= right );
}

Die Schleife 'while ( a[left]< acrit ) left++;' läuft nicht aus dem Anfangsintervall [left0, right0] heraus. Beim ersten Mal kommt sie spätestens bei left == k0zum Stoppen. Danach wird vertauscht, so daß ein begrenzender Wert nach rechts von left kommt, oder der Gesamtdurchlauf ist beendet. Entsprechendes gilt für die while-Schleife mit right.

Die Schleifenbedingung 'while ( a[left] < x )' führt zum Tauschen von Werten, die >= acrit sind, insbesondere wird auch im Fall == acrit getauscht, was eigentlich überflüssig ist. Man betrachte dazu ein Beispiel, in dem einige Werte mit acrit übereinstimmen. Man könnte naiv versuchen, die überflüssigen Vertauschungen zu vermeiden, indem die Schleifenbedingung wie folgt verschärft: 'while ( a[left] <= x )'. Dies Variante kann aber zum Hinauslaufen aus dem Suchintervall führen, man betrachte Das Beispiel eines Arrays mit lauter gleichen Werten. Man müßte also eine kompliziertere Schleifenbedingung formulieren (welche?), die ihrereits Zeit kosten würde. Wirth zieht es vor, Vertauschungen von Werten im Fall == acrit in Kauf zu nehmen.

Wir erzielen insgesamt folgendes (sogenannte Invariante der Schleife):

a[k] <= acrit für k = left0,...,left-1 a[k] >= acrit für k = right+1,...,right0

Das ist zu Anfang - vor der Hauptschleife - richtig und nach jedem Schleifenschritt.

Damit können wir die beiden durch die Vorsortierung entstandenen Teilintervalle I1 und I2 wie folgt definieren: [left0, right] und [left, right0], vgl. Zeichnung.

Wegen 'right < left' bei Verlassen der Hauptschleife haben wir 'right <= left-1', und damit gilt nach obiger Invariante, daß die Werte auf [left0, right] <= acrit sind. Ebenso haben wir 'left >= right+1', und es gilt nach der Invariante, daß die Werte auf [left, right0] >= acrit sind.

Bemerkung 1: Wenn right < left -1 gilt (kann vorkommen), dann liegen zwischen den Teilintervallen I1 und I2 ein oder mehrere Werte ak mit ak == acrit. Diese werden dann beim weiteren Sortieren automatisch nicht mehr berücksichtigt.

Bemerkung 2: Erzielen eines Fortschritts Die angestrebte Vorsortierung auf den Teilintervallen liegt offentsichtlich vor, vgl. Invariante und Bemerkung 1. Der vollständige Quicksort wird den (Vor-)Sortierschritt auf die Teilintervalle I1 und I2 anwenden, siehe dort. Um nachzuweisen, daß man tatsächlich einen Fortschritt erzielt, der in endlich vielen Sortierschritten zum Erfolg führt, muß man zeigen, daß die Teilintervalle kleiner werden, daß also nicht der Fall I1 == I & I2 leer bzw. I2 == I & I1 leer auftreten kann. Betrachten wir die Möglichkeit, daß am Ende des Sortierschritts I2 leer ist, also right == right0 ist. Dann haben wir keinen Austauschschritt durchlaufen, sonst wäre right < right0. Daraus folgt, daß left im ersten Durchlauf der Hauptschleife in der while-Schleife mindestens bis auf right+1 bzw. right0+1 hochgezählt wird, andernfalls würde die Hauptschleife ja nicht verlassen. Daraus folgt, daß alle Werte a[k] des Intervalls kleiner sind als der Vergleichswert a[k0], was nicht sein kann.

Bemerkung 3: Im Paartausch innerhalb der der Hauptschleife kann man durchaus den nutzlosen Tausch im Falle left == right vermeiden, indem man auf left < right abfragt. Das kostet aber eine zweite Abfrage, weil man das Hochzählen der Intervallgrenzen left und right auch im Fall left == right machen muß.