Arrays sortieren — Selection Sort, Bubble Sort, etc.
1. Uberblick
Sortieren ist das Anordnen mehrerer Elemente nach festgelegten Kriterien. Damit Sortierung möglich ist, muss die Vergleichbarkeit in folgender Form möglich sein: Wenn Fritz (der Mittlere) jünger als Karl (der Älteste) ist und Evi (die Jüngste) jünger als Fritz, dann ist Evi auch jünger als Karl. Diese Art der Vergleichbarkeit ist Voraussetzung, dass Sortierung logisch möglich ist.
2. Selection Sort
Eine der einfachst verständlichen Sortier-Algorithmen ist der Selection-Sort-Algorithmus. Dieser arbeitet folgendermaßen:
-
Finde das kleinste Element in der Liste, tausche es mit dem Element an Position 0
-
Damit ist das kleinste Element schon an der richtigen Position
-
Wiederhole den Vorgang für den Array-Rest (von Position 1 bis Ende). Damit ist das zweitkleinste Element an Position 1 gespeichert.
-
Dies wird weiter durchgeführt, bis der Array-Rest nur mehr Länge 1 hat - damit ist kein Sortieren mehr möglich.
TODO: freeIdx-Konzept einsetzen
public void selectionSort() {
printArrayTabular("selectionSort VOR Sortierung", 5);
for (int i = 0; i < arr.length; i++) {
int minValIdx = findMinValPos(i, arr.length);
tauschen(i, minValIdx);
}
printArrayTabular("selectionSort NACH Sortierung", 5);
}
// bestimmen der POSITION des kleinsten Wertes
//.. 'endIdxExcl' der erste NICHT MEHR verwendete Array-Index
public int findMinValPos(int anfIdx, int endIdxExcl) {
if (anfIdx < 0 || anfIdx >= endIdxExcl || endIdxExcl > arr.length) {
return -1;
}
int minValPos = anfIdx; // provisorisch minValPos auf anfIdx setzen
for (int i = anfIdx + 1; i < endIdxExcl; i++) {
if (arr[i] < arr[minValPos]) {
minValPos = i;
}
}
return minValPos;
}
// Tauschen der Werte an den beiden Positionen ("Dreieckstausch")
public void tauschen(int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
public void printArrayTabular(String title, int cols) {
System.out.println(title);
for (int i = 0; i < arr.length; i++) {
if (i > 0 && i%cols == 0) {
System.out.println();
}
System.out.print(" " + arr[i]);
}
System.out.println();
}3. Bubble Sort
Ein einfaches, aber auch nicht sehr effizientes Sortierverfahren ist Bubblesort, (Austauschsortieren).
Die Liste wird immer wieder durchlaufen und sukzessive alle Nachbarn verglichen. Wenn deren Sortierung nicht passt, werden sie ausgetauscht (z.B. Hilfsmethode oneBubble(): boolean für einen solchen Durchlauf, Rückgabewert false wenn kein Tausch mehr aufgetreten ist).
Die Wiederholung solcher Durchläufe wird beendet, sobald kein einziger Tausch mehr erfolgt ist.
public class BubbleSort
{
private float[] values;
public BubbleSort(float[] values) {
this.values = values;
}
/* Ablaufbeispiel sort():
* 7, 5, 8, 2 (Ausgangswerte)
* 5, 7, 8, 2
* 5, 7, 8, 2
* 5, 7, 2, 8 (bis hierher erster 'oneBubble'-Durchlauf)
*
* 5, 2, 7, 8 (nächster 'oneBubble'-Durchlauf)
*
* 2, 5, 7, 8 (letzter 'oneBubble'-Durchlauf - weil keine Änderungen mehr)
*/
public void sort() {
while (oneBubble(0, values.length)) {
// leer - alles passiert in oneBubble(..) oben!!!
}
// boolean ready = false; // Alternative:
// while (!ready) { ready = oneBubble(0, values.length); }
}
public boolean oneBubble(int startIdx, int stopIdxExcl) {
boolean changed = false;
for (int i = startIdx; i < stopIdxExcl - 1; i++) {
if (values[i] > values[i+1]) {
tauschen(i, i+1);
changed = true;
}
}
return changed; // liefert false, wenn KEINE Änderung mehr nötig -> sortiert!
}
// Tauschen der Werte an den beiden Positionen ("Dreieckstausch")
public void tauschen(int idx1, int idx2) {
float tmp = values[idx1];
values[idx1] = values[idx2];
values[idx2] = tmp;
}
public void printArray(String title) {
int freeIdx = values.length; // entfernen, falls freeIdx in Verwendung!
System.out.format("=== %s, Kapazität %d, Füllstand %d: ===%n",
title, values.length, freeIdx);
for (int i = 0; i < freeIdx; i++) { // statt freeIdx hier auch direkt values.length
System.out.format(" %1.2f", values[i]);
}
System.out.println();
}
public static void testen() { // STATISCHE Methode!
BubbleSort bbs = new BubbleSort(new float[] {99.9f, 0, 17, -3.0f});
bbs.printArray("Nach Erzeugung");
bbs.sort();
bbs.printArray("Nach Sortierung");
}
}4. Insertion Sort
Der Algorithmus Insertion-Sort ist recht intuitiv und entspricht im wesentlichen der Herangehensweise, wenn man z.B. Zettel mit Datumsangabe (heruntergefallene Lose-Blatt-Mitschrift), Spielkarten, Worte, etc. sortieren muss.
Der Ablauf:
-
Vorbereitung Ausgangsmaterial: Bereitlegen des "Haufens" an beliebig angeordneten Elementen und Zählen der Anzahl (Java: z.B. Array mit zufälligen Werten füllen). Es könnten die Werte aber auch sukzessive mittels "Scanner-Klasse" eingegeben werden, dann sollte zur Minimierung der Komplexität nur die Maximal-Anzahl festgelegt werden, um die Array-Länge statisch festlegen zu können). Weiters Vorbereiten des Ablage-Arrays, in dem die sortierten Elemente abgelegt werden sollen.
-
Start: Beliebiges Element aus "Haufen" wählen und "links" an erste Position (wo das kleinste Element liegen soll) hinlegen (man könnte auch in umgekehrter Richtung vorgehen).
-
Nächstes (beliebiges) Element wählen. Wenn neues kleiner als erstes Element, erstes und Element eine Position nach rechts schieben, neues Element an erste Position,
-
Weiteres Element wählen, von links beginnend vergleichen. Sobald das neue Element kleiner ist, alle ab dieser Position liegenden, bereits sortierten Elemente um eins nach rechts verschieben, um Platz für das neue Element zu schaffen. Dieses in die nun freigemachte Position einfügen.
-
Vorgang wiederholen, bis der "Haufen" leer ist. Damit liegen alle Elemente sortiert im Ablage-Array.
Dabei wichtig für Optimierung: bei Gleichheit NICHT einfügen, sondern weiter probieren, bis das neue Element wirklich kleiner ist. es könnte ja vorkommen, dass viele gleiche Elemente aufeinanderfolgen. Je später man "Platz macht", desto weniger Aufwand, da die zu verschiebenden Elemente immer weniger werden (im Extremfall sind ALLE danach gleich groß und wir können einfach ohne Verschiebung hinten anfügen)
Für die Implementierung in Programmiersprachen ist es wichtig, die Vergleichsoperation als eigene Methode zu implementieren, dann kann die Sortierungsrichtung (auf-/absteigend) und bei Objekten auch das/die Sortier-Attribut(e) - nach Name, Alter, Gewicht, Haarfarbe, etc. leicht angepasst werden - es muss nur die Vergleichsmethode verändert werden - der Algorithmus bleibt identisch.
//TODO: Code einfügen