Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


8. Elementare Sortierverfahren



Spielregeln

Bevor wir einige spezifische Algorithmen betrachten, wird es von Nutzen sein, einige allgemeine Termini und grundlegende Annahmen für Sortieralgorithmen zu erörtern. Wir werden Verfahren zum Sortieren von Dateien (files) mit Datensätzen (records) betrachten, welche Schlüssel (keys) enthalten. Die Schlüssel, die nur ein Teil der Datensätze sind (oft ein kleiner Teil), werden verwendet, um das Sortieren zu steuern. Die Aufgabe des Sortierverfahrens besteht darin, die Datensätze so umzuordnen, daß ihre Schlüssel gemäß einer gewissen klar definierten Ordnung (gewöhnlich nach der numerischen oder alphabetischen Reihenfolge) geordnet sind.

Wenn die zu sortierende Datei im Speicher untergebracht werden kann (oder, unter unseren Bedingungen, wenn sie in einem Feld (array) von Pascal gespeichert werden kann), so spricht man von einer internen Sortiermethode. Das Sortieren von Dateien auf einem Magnetband oder einer Magnetplatte wird externes Sortieren genannt. Der Hauptunterschied zwischen den beiden Typen besteht darin, daß bei einem internen Sortierverfahren ein leichter Zugriff auf jeden Datensatz möglich ist, während ein externes Sortierverfahren den Zugriff auf die Datensätze sequentiell oder zumindest in großen Blöcken realisieren muß. In Kapitel 13 werden wir einige externe Sortierverfahren betrachten, doch die meisten der von uns behandelten Algorithmen betreffen interne Sortiermethoden.

Wie üblich, ist der wichtigste Parameter der Leistungsfähigkeit, der uns interessiert, die Laufzeit unserer Sortieralgorithmen. Die ersten vier Methoden, die wir in diesem Kapitel betrachten, benötigen für das Sortieren von N Elementen eine Zeit, die proportional zu N2 ist, während weiterentwickelte Verfahren N Elemente in einer Zeit sortieren können, die zu N log N proportional ist. (Es läßt sich zeigen, daß kein Sortieralgorithmus mit weniger als N log N Vergleichen zwischen Schlüsseln auskommt.) Nach der Untersuchung der einfachen Methoden betrachten wir eine weiterentwickelte Methode, die in einer zu N3/2 proportionalen Zeit oder schneller ablaufen kann, und wir werden sehen, daß es Verfahren gibt, die digitale Eigenschaften von Schlüsseln ausnutzen und dadurch eine Gesamtlaufzeit erzielen, die proportional zu N ist.

Der zusätzliche Speicherplatz, der durch einen Sortieralgorithmus belegt wird, ist der zweite wichtige Faktor, den wir berücksichtigen müssen. Grundsätzlich lassen sich die Verfahren in drei Typen einteilen: Verfahren, die am Ort sortieren und keinen zusätzlichen Speicherplatz benötigen, außer vielleicht für einen kleinen Stapel oder eine kleine Tabelle; Verfahren, bei denen eine Darstellung mittels verketteter Liste benutzt wird, so daß sie im Speicher N zusätzliche Worte für Listenzeiger benötigen; sowie Verfahren, die genügend zusätzlichen Speicherplatz benötigen, um eine weitere Kopie des zu sortierenden Feldes zu speichern.

Ein weiteres Merkmal von Sortierverfahren, welches in der Praxis manchmal von Bedeutung ist, ist die Stabilität. Ein Sortierverfahren wird stabil genannt, wenn es die relative Reihenfolge gleicher Schlüssel in der Datei beibehält. Wenn zum Beispiel eine alphabetisch geordnete Liste von Studenten eines Kurses nach deren Noten sortiert wird, so liefert eine stabile Methode eine Liste, in der Studenten mit der gleichen Note nach wie vor in alphabetischer Reihenfolge aufgeführt werden; eine nichtstabile Methode erzeugt dagegen im allgemeinen eine Liste, in der von der alphabetischen Reihenfolge keine Spur mehr vorhanden ist. Die meisten einfachen Methoden sind stabil, die meisten der bekannten komplizierten Algorithmen jedoch nicht. Wenn die Stabilität von Bedeutung ist, so kann sie erzwungen werden, indem vor dem Sortieren jeder Schlüssel mit einem kleinen Index versehen wird oder auf irgendeine andere Weise verlängert wird. Stabilität wird leicht als gegeben angenommen; Anwender reagieren oft mit Verwunderung auf die unangenehmen Effekte der Instabilität. In Wirklichkeit gewährleisten nur wenige Methoden Stabilität, ohne wesentlich mehr Zeit oder Speicherplatz zu benötigen.

Das folgende Programm für das Sortieren von drei Datensätzen dient dem Ziel, die allgemeinen Konventionen zu illustrieren, die wir benutzen werden. Speziell das Hauptprogramm ist ein spezifischer Weg, um ein Programm auszuführen, das nur für N = 3 funktioniert; das entscheidende ist, daß in dieses »Treiber«-Programm jedes beliebige Sortierprogramm anstelle von sort3 eingesetzt werden könnte.

    program threesort(input,output);
    const maxN=100;
    var a: array[1..maxN] of integer;
        N,i: integer;
    procedure sort3;
      var t: integer;
      begin
      if a[1]>a[2] then
        begin t:=a[1]; a[1]:=a[2]; a[2]:=t end;
      if a[1]>a[3] then
        begin t:=a[1]; a[1]:=a[3]; a[3]:=t end;
      if a[2]>a[3] then
        begin t:=a[2]; a[2]:=a[3]; a[3]:=t end;
      end;
    begin
    readln(N);
    for i:=1 to N do read(a[i]);
    if N=3 then sort3;
    for i:=1 to N do write(a[i]);
    writeln
    end.

Die drei Zuweisungsbefehle, die jedem if folgen, implementieren in Wirklichkeit eine »Austausch«-Operation. Anstatt einen Prozeduraufruf zu verwenden, ziehen wir es vor, den Code für solche Austauschoperationen auszuschreiben, da sie für viele Sortierprogramme eine fundamentale Rolle spielen und oft in der inneren Schleife enthalten sind.

Um uns auf algorithmische Fragen zu konzentrieren, arbeiten wir mit Algorithmen, die einfach Felder von ganzen Zahlen der Größe nach sortieren. Im allgemeinen ist es sehr einfach, solche Algorithmen für den Einsatz in praktischen Anwendungen anzupassen, in denen umfangreiche Schlüssel oder Datensätze auftreten. Grundsätzlich realisieren Sortierprogramme den Zugriff auf Datensätze auf zweierlei Weise: Entweder es erfolgt ein Zugriff auf Schlüssel zum Zwecke des Vergleichs, oder ein Zugriff auf ganze Datensätze, um sie zu bewegen. Die Mehrzahl der Algorithmen, die wir untersuchen werden, können unter Verwendung dieser beiden Operationen für beliebige Datensätze formuliert werden. Wenn die zu sortierenden Datensätze groß sind, sollte man normalerweise vermeiden, sie umherzuschieben, indem man ein »indirektes Sortieren« vornimmt: Hierbei werden die Datensätze selbst nicht notwendigerweise umgeordnet, sondern vielmehr wird ein Feld von Zeigern (oder Indizes) so umgeordnet, daß der erste Zeiger auf den kleinsten Datensatz zeigt usw. Die Schlüssel können entweder mit den Datensätzen (wenn sie umfangreich sind) oder mit den Zeigern (wenn sie klein sind) gespeichert werden. Falls erforderlich, können die Datensätze dann nach dem Sortieren umgeordnet werden, wie weiter unten in diesem Kapitel beschrieben wird.

Das obige Programm sort3 benutzt eine sogar noch stärker eingeschränkte Variante des Zugriffs auf die Datei: Es handelt sich um drei Anweisungen der Form »vergleiche zwei Datensätze und tausche sie, falls erforderlich, aus, so daß derjenige mit dem kleineren Schlüssel vorn steht«. Programme, die auf solche Anweisungen beschränkt sind, sind deswegen von Interesse, weil sie für eine hardwaremäßige Implementation gut geeignet sind. Wir werden uns dieser Frage in Kapitel 40 ausführlicher zuwenden.

Wenn wir Programme benutzen, die einfach mit einem globalen Feld operieren, vernachlässigen wir »Schnittstellenprobleme«, die bei manchen Programmierumgebungen schwierig sein können. Sollte das Feld der Sortier-Routine als Parameter übergeben werden? Kann die gleiche Sortier-Routine verwendet werden, um Felder von ganzen Zahlen und Felder von reellen Zahlen zu sortieren (und Felder von beliebig komplexen Datensätzen)? Sogar bei unseren einfachen Annahmen müssen wir das Fehlen von dynamischen Feldgrößen in Pascal umgehen, indem wir im voraus ein Maximum deklarieren. In Programmierumgebungen der Zukunft wird es leichter sein, solche Probleme zu lösen, als in denen der Vergangenheit und der Gegenwart. Zum Beispiel haben einige moderne Sprachen sehr gut entwickelte Möglichkeiten zur Bündelung von Programmen zu großen Systemen. Andererseits sind solche Mechanismen für viele Anwendungen nicht wirklich notwendig: Kleine Programme, die direkt mit globalen Feldern arbeiten, haben viele Anwendungen, und einige Betriebssysteme machen es recht einfach, einfache Programme wie das obige zusammenzusetzen, die als »Filter« zwischen ihren Eingaben und ihren Ausgaben dienen. Offensichtlich gelten diese Bemerkungen für viele andere Algorithmen, die wir untersuchen werden, wenn auch die genannten Effekte vielleicht bei Sortieralgorithmen am deutlichsten sichtbar werden.

Manche Programme verwenden einige weitere globale Variablen. Deklarationen, die nicht offensichtlich sind, werden mit in den Programmcode aufgenommen. Weiterhin werden wir gelegentlich annehmen, daß sich die Feldgrenzen bis 0 oder N+1 erstrecken, um spezielle Schlüssel zu speichern, die von einigen der Algorithmen verwendet werden. Oft werden wir für Beispiele anstelle von Zahlen Buchstaben benutzen; diese werden in der offensichtlichen Weise unter Verwendung der in Pascal vorhandenen »Umwandlungsfunktionen« ord und chr behandelt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]