Kapitel 3: Sortieralgorithmen

Das Sortieren ist der Prozess des Umordnens einer Sequenz von Objekten, um sie in eine logische Reihenfolge zu bringen. Zum Beispiel präsentiert Ihre Kreditkartenabrechnung Transaktionen in chronologischer Reihenfolge, und Sie stellen Ihre Bücher auf Ihrem Bücherregal alphabetisch nach Autor und Titel auf. Sortieren ist eine grundlegende Operation in der Informatik und spielt in vielen Anwendungen eine entscheidende Rolle. Es gibt eine Vielzahl klassischer Sortieralgorithmen, die unterschiedliche Ansätze zu diesem Problem verkörpern.

In diesem Kapitel betrachten wir mehrere klassische Sortierverfahren und eine wichtige Datenstruktur, die als Prioritätswarteschlange bekannt ist. Wir beginnen mit einer Diskussion einiger elementarer Sortierverfahren, darunter Auswahlsortierung, Einfügungssortierung und Shellsortierung. Diese Methoden werden in vielen Anwendungen angemessen eingesetzt, aber für große Probleme wenden wir uns der Mergesortierung und Quicksortierung zu, zwei rekursive Sortieralgorithmen, die verwendet werden können, um riesige Mengen von Elementen zu sortieren. Wir schließen mit einer Diskussion von Prioritätswarteschlangen und ihrer Verwendung beim Sortieren und in anderen Anwendungen ab.

Elementare Sortierverfahren

Die einfachsten Sortieralgorithmen führen die folgenden Operationen durch:

• Auswahlsortierung: Finden Sie den kleinsten Eintrag und tauschen Sie ihn mit dem ersten Eintrag aus, dann finden Sie den zweitkleinsten Eintrag und tauschen Sie ihn mit dem zweiten Eintrag aus, usw.
• Einfügungssortierung: Nehmen Sie jeden Eintrag der Reihe nach und fügen Sie ihn an der richtigen Position unter den bereits berücksichtigten Einträgen ein (wobei diese sortiert bleiben).

Diese Operationen spiegeln wider, wie Menschen typischerweise Sortieraufgaben durchführen, und sind für kleine Problemgrößen effektiv. Sie skalieren jedoch nicht gut und werden für das Sortieren großer Arrays unpraktisch.

Auswahlsortierung

Die Auswahlsortierung ist ein einfacher Sortieralgorithmus, der wie folgt funktioniert: Finden Sie zunächst das kleinste Element im Array und tauschen Sie es mit dem ersten Eintrag aus (mit sich selbst, wenn der erste Eintrag bereits der kleinste ist). Finden Sie dann das nächstkleinste Element und tauschen Sie es mit dem zweiten Eintrag aus. Fahren Sie auf diese Weise fort, bis das gesamte Array sortiert ist.

Die innere Schleife der Auswahlsortierung...Here is the German translation of the provided markdown file, with the code comments translated:

Sortieren ist eine Methode, um die minimalen Elemente im unsortieren Teilarray a[i..N-1] zu finden. Der Index des minimalen Elements wird in min gespeichert. Dann wird a[i] mit a[min] ausgetauscht, was das minimale Element an seine endgültige Position bringt. Während der Index i von links nach rechts wandert, sind die Elemente zu seiner Linken in sortierter Reihenfolge im Array und werden nicht mehr berührt.

Hier ist eine Implementierung von Selectionsort in Java:

public static void selectionSort(Comparable[] a) {
    // Länge des Arrays
    int N = a.length;
    for (int i = 0; i < N; i++) {
        // Index des minimalen Elements
        int min = i;
        for (int j = i+1; j < N; j++) {
            // Finde das minimale Element
            if (less(a[j], a[min])) min = j;
        }
        // Tausche das minimale Element an die richtige Stelle
        exch(a, i, min);
    }
}

Selectionsort verwendet etwa ~N^2/2 Vergleiche und N Austausche, um ein Array der Länge N zu sortieren. Die Laufzeit ist unempfindlich gegenüber der Eingabe - es dauert etwa genauso lange, Selectionsort für ein bereits sortiertes Array oder ein Array mit gleichen Schlüsseln auszuführen wie für ein zufällig sortiertes Array.

Insertionsort

Insertionsort ist ein weiterer einfacher Sortieralgorithmus, der das endgültige sortierte Array Schritt für Schritt aufbaut. Er ist für große Arrays deutlich weniger effizient als fortgeschrittenere Algorithmen wie Quicksort, Heapsort oder Mergesort, hat aber einige Vorteile:

• Er ist effizient für kleine Datensätze.
• Er ist in der Praxis effizienter als Selectionsort.
• Er ist stabil, d.h. er ändert die relative Reihenfolge von Elementen mit gleichen Schlüsseln nicht.
• Er ist in-place, d.h. er benötigt nur eine konstante zusätzliche Speicherplatz O(1).
• Er ist online, d.h. er kann eine Liste sortieren, während er sie empfängt.

Hier ist eine Implementierung von Insertionsort in Java:

public static void insertionSort(Comparable[] a) {
    // Länge des Arrays
    int N = a.length;
    for (int i = 1; i < N; i++) {
        // Füge das Element an der Stelle i an der richtigen Stelle ein
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // Tausche das Element an Stelle j mit dem Element an Stelle j-1
            exch(a, j, j-1);
        }
    }
}

Die innere Schleife von Insertionsort verschiebt größere Elemente eine Position nach rechts, um Platz für das aktuelle Element zu schaffen.Hier ist die deutsche Übersetzung der Markdown-Datei, wobei die Kommentare in den Codeblöcken übersetzt wurden:

Die Laufzeit von Insertionsort hängt von der anfänglichen Reihenfolge der Elemente in der Eingabe ab. Wenn zum Beispiel das Array groß ist und seine Einträge bereits in Ordnung (oder fast in Ordnung) sind, ist Insertionsort viel, viel schneller als wenn die Einträge zufällig oder in umgekehrter Reihenfolge angeordnet sind.

Shellsort

Shellsort ist eine einfache Erweiterung von Insertionsort, die an Geschwindigkeit gewinnt, indem sie den Austausch von Arrayeinträgen, die weit auseinander liegen, erlaubt, um teilweise sortierte Arrays zu erzeugen, die effizient sortiert werden können, schließlich durch Insertionsort.

Die Idee ist, das Array so umzuordnen, dass es die Eigenschaft hat, dass jeder h-te Eintrag (von überall her) eine sortierte Teilfolge ergibt. Ein solches Array wird als h-sortiert bezeichnet. Anders ausgedrückt, ein h-sortiertes Array besteht aus h unabhängigen sortierten Teilfolgen, die miteinander verwoben sind. Durch h-Sortieren für einige große Werte von h können wir Elemente im Array über große Entfernungen bewegen und es so einfacher machen, für kleinere Werte von h zu h-sortieren. Eine solche Vorgehensweise für eine beliebige Folge von Werten von h, die mit 1 endet, wird ein sortiertes Array ergeben: Das ist Shellsort.

Hier ist eine Implementierung von Shellsort in Java:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // Bewegt ein Element nach oben im Heap
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // Bewegt ein Element nach unten im Heap
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private booleaHier ist die deutsche Übersetzung der Markdown-Datei, wobei die Kommentare in den Codeblöcken übersetzt wurden:
 
n weniger(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

Dieser Code implementiert einen max-orientierten binären Heap unter Verwendung eines Arrays pq, um den heap-geordneten vollständigen binären Baum zu speichern. Die Operationen insert() und delMax() erhalten die Heap-Invariante, indem sie die Hilfsmethoden swim() und sink() verwenden, um die Heap-Ordnung wiederherzustellen, indem sie Schlüssel mit einem Elternteil, das größer als ein Kind ist, oder einem Kind, das größer als sein Elternteil ist, austauschen.

Stoppuhr

Ein nützlicherer abstrakter Datentyp ist eine einfache und effektive Abstraktion für eine Stoppuhr, die auf der gegenüberliegenden Seite gezeigt wird. Um sie zu verwenden, erstellen Sie ein Stoppuhr-Objekt, wenn Sie den Timer starten möchten, und verwenden Sie dann die Methode elapsedTime(), um die seit der Erstellung des Objekts verstrichene Zeit in Sekunden zu erhalten. Die Implementierung verwendet System.currentTimeMillis() von Java, um die aktuelle Zeit in Millisekunden seit Mitternacht des 1. Januar 1970 zu erhalten.

Die Instanzvariable start zeichnet die Zeit auf, zu der die Stoppuhr erstellt wurde, und elapsedTime() verwendet start, um die verstrichene Zeit zu berechnen. Der gezeigte Client ist typisch: Er führt eine Berechnung durch und verwendet eine Stoppuhr, um zu messen, wie lange die Berechnung dauert. Der Datentyp Stoppuhr ist eine effektive Abstraktion, da er das Konzept einer Stoppuhr (die Schnittstelle) von der Implementierung (unter Verwendung von System.currentTimeMillis() von Java) trennt. Diese Trennung von Schnittstelle und Implementierung ist ein grundlegendes Merkmal abstrakter Datentypen, das wir in jedem ADT in diesem Buch sehen werden.

Zusammenfassung

Abstrakte Datentypen sind ein wesentliches Element der objektorientierten Programmierung, die in der modernen Programmierung weit verbreitet sind. In diesem Abschnitt haben wir Folgendes gesehen:

• Definieren eines abstrakten Datentyps als Java-Klasse mit Instanzvariablen zur Definition der Datentypwerte und Instanzmethoden zur Implementierung der Operationen auf diesen Werten.
• Entwickeln mehrerer Implementierungen derselben API unter Verwendung unterschiedlicher Darstellungen desselben abstrakten Datentyps.Hier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst wurde nicht übersetzt.

Aktivitäten im Zusammenhang mit abstrakten Datentypen.

• Unterscheidung zwischen APIs, Clients und Implementierungen eines abstrakten Datentyps.
• Entwicklung von APIs für abstrakte Datentypen.
• Entwicklung von Clients und Testclients für den Einsatz bei Tests und Fehlersuche.
• Überlegungen zur Korrektheit einer Implementierung eines abstrakten Datentyps unter Verwendung von Assertions.
• Vergleich der Leistung verschiedener Implementierungen derselben API.

Diese Aktivitäten sind ein wesentlicher Bestandteil der Entwicklung jedes Java-Programms. Jedes Java-Programm, das wir schreiben, wird den Einsatz abstrakter Datentypen aus Bibliotheken beinhalten; viele werden auch die Entwicklung neuer abstrakter Datentypen umfassen. Im nächsten Abschnitt betrachten wir drei grundlegende abstrakte Datentypen, die wesentliche Komponenten in einer Vielzahl von Programmen sind, und in Abschnitt 1.4 untersuchen wir den Prozess der Analyse der Leistungsmerkmale von Implementierungen im Detail.