Sortieralgorithmen

Es gibt sehr viele Sortierverfahren, die unterschiedlich effizient arbeiten.

Einige Sortierverfahren benötigen neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz.

Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).

Die wichtigsten Sortieralgorithmen seien hier nur genannt:
Binary Tree Sort, Bubblesort, Countingsort, Cocktailsort, Gnomesort, Heapsort, Insertionsort, Introsort, Mergesort, Quicksort, Selectionsort, Shellsort, Slowsort, Smoothsort, Radixsort, Stoogesort

Die beiden einfachsten Sortierverfahren wollen wir hier kennenlernen.

Prinzip:

• Das 1. Element wird mit allen folgenden der Reihe nach verglichen.
• Ist ein Feldelement kleiner als das 1., werden beide Feldelemente getauscht. Damit steht das kleinste Feldement an 1. Stelle.
• Dann wird das 2. Element mit allen folgenden der Reihe nach verglichen.
• Ist ein Feldelement kleiner als das 2., werden beide Feldelemente getauscht. Damit steht das zweitkleinste Feldement an 2. Stelle.
• Mit dem 3., 4., ... bis zum vorletzten Feldelement wird genau so verfahren.

Beispiel:

Vergleich des 1. Elementes mit den folgenden
5	3	6	1	4	Tausch
3	5	6	1	4	kein Tausch
3	5	6	1	4	Tausch
1	5	6	3	4	kein Tausch
Vergleich des 2. Elementes mit den folgenden
1	5	6	3	4	kein Tausch
1	5	6	3	4	Tausch
1	3	6	5	4	kein Tausch
Vergleich des 3. Elementes mit den folgenden
1	3	6	5	4	Tausch
1	3	5	6	4	Tausch
Vergleich des 4. Elementes mit dem 5.
1	3	4	6	5	Tausch
Das Array ist jetzt fertig sortiert
1	3	4	5	6

Struktogramm / Syntax:

Beispiel: Aufsteigendes Sortieren von 50 Zahlen im Feld zahl(49)

For i = 0 To 48   For j = i + 1 To 49    If zahl(i) > zahl(j) Then     '-----Tausch-----     h = zahl(i)     zahl(i) = zahl(j)     zahl(j) = h    End If   Next j Next i

Prinzip:

Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und
vertauscht sie, falls sie in der falschen Reihenfolge vorliegen.
Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Reihe.

Der BubbleSort-Algorithmus eignet sich vor allen bei vorsortierten Datenreihen.

Beispiel:

1. Durchlauf
5	3	6	1	4	Tausch
3	5	6	1	4	kein Tausch
3	5	6	1	4	Tausch
3	5	1	6	4	Tausch
2. Durchlauf
3	5	1	4	6	kein Tausch
3	5	1	4	6	Tausch
3	1	5	4	6	Tausch
3. Durchlauf
3	1	4	5	6	Tausch
1	3	4	5	6	kein Tausch
4. Durchlauf
1	3	4	5	6	kein Tausch
Das Array ist jetzt fertig sortiert
1	3	4	5	6

Struktogramm / Syntax:

Beispiel: Aufsteigendes Sortieren von 50 Zahlen im Feld zahl(49)

n = 49 Do   vertauscht = false   For i = 0 To n - 1     If zahl(i) > zahl(i + 1) Then       '-----Tausch-----       h = zahl(i)       zahl(i) = zahl(i + 1)       zahl(i + 1) = h       vertauscht = true     End If   Next i   n = n - 1 Loop While vertauscht = true And n >= 1

Aufgabe

• Vergleich BubbleSort- / SelectSort-Algorithmus