Sortieralgorithmen

Sortieralgorithmen sind Verfahren, mit denen Daten in eine bestimmte Reihenfolge gebracht werden, z. B. aufsteigend oder absteigend.

Sie werden verwendet, um Zahlen, Wörter oder Datensätze zu ordnen.

Ziel von Sortieralgorithmen

Sortieralgorithmen helfen dabei:

• Daten übersichtlich darzustellen
• schneller nach Werten zu suchen
• Daten für weitere Verarbeitung vorzubereiten

Bekannte Sortieralgorithmen

Es gibt viele verschiedene Sortierverfahren, zum Beispiel:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Sie unterscheiden sich vor allem in:

• Geschwindigkeit
• Speicherbedarf
• Verständlichkeit

Bubble Sort

Bubble Sort ist ein einfaches Sortierverfahren.

Dabei werden immer zwei benachbarte Elemente verglichen. Stehen sie in der falschen Reihenfolge, werden sie vertauscht.

Dieser Vorgang wird so oft wiederholt, bis alle Elemente richtig sortiert sind.

Der Name Bubble Sort kommt daher, dass die größten Elemente bei jedem Durchlauf wie Blasen („bubbles“) nach oben bzw. ans Ende der Liste wandern.

Funktionsweise

Beispiel:

5  2  4  1

1. Vergleiche 5 und 2 → tauschen

2  5  4  1

2. Vergleiche 5 und 4 → tauschen

2  4  5  1

3. Vergleiche 5 und 1 → tauschen

2  4  1  5

Nach dem ersten Durchlauf steht die größte Zahl ganz rechts.

Dann beginnt der nächste Durchlauf:

1. Vergleiche 2 und 4 → richtig 2. Vergleiche 4 und 1 → tauschen

2  1  4  5

Nächster Durchlauf:

1. Vergleiche 2 und 1 → tauschen

1  2  4  5

Jetzt ist die Liste sortiert.

Beispiel in Java

int[] zahlen = {5, 2, 4, 1};

// Äußere Schleife: Anzahl der Durchläufe
// Nach jedem Durchlauf steht das größte Element an der richtigen Stelle ganz rechts
for (int i = 0; i < zahlen.length - 1; i++) {

    // Innere Schleife: vergleicht benachbarte Elemente
    // "- i", weil die letzten i Elemente bereits sortiert sind
    for (int j = 0; j < zahlen.length - 1 - i; j++) {

        // Vergleich: ist das linke Element größer als das rechte?
        if (zahlen[j] > zahlen[j + 1]) {

            // Tauschen der beiden Elemente
            int temp = zahlen[j];        // speichert das linke Element
            zahlen[j] = zahlen[j + 1];  // rechtes Element nach links
            zahlen[j + 1] = temp;       // gespeichertes Element nach rechts
        }
    }
}

Eigenschaften von Bubble Sort

• leicht verständlich
• einfach zu programmieren
• langsam bei großen Datenmengen
• gut für kleine Beispiele und zum Lernen

Vorteile

• sehr einfaches Prinzip
• gut zum Einstieg in Sortieralgorithmen
• keine komplizierten Datenstrukturen nötig

Nachteile

• viele Vergleiche
• viele Vertauschungen
• ineffizient bei großen Listen

Andere Sortieralgorithmen (kurz)

Selection Sort

Sucht in jedem Durchlauf das kleinste Element und setzt es an die richtige Position.

Insertion Sort

Fügt Elemente nach und nach an der richtigen Stelle in eine bereits teilweise sortierte Liste ein.

Merge Sort

Teilt die Liste in kleinere Teile und fügt sie anschließend sortiert wieder zusammen.

Quick Sort

Wählt ein Vergleichselement (Pivot) und teilt die Liste in kleinere und größere Werte auf.

Kurzmerksatz

Sortieralgorithmen bringen Daten in eine bestimmte Reihenfolge. Bubble Sort ist einfach zu verstehen, aber langsam.