Sortieralgorithmen

Oft hat man das Problem, dass einge große Menge an Daten in eine optimale Reihenfolge gebracht werden muss. Um dies zu realisieren gibt es einige bekannte Sortieralgorithmen, die sich in der Art, wie sie funktionieren und in ihrer Laufzeit unterscheiden. Im folgenden sollen die bekanntesten Verfahren einmal vorgestellt werden.

Insertionsort

Struktogramm Insertionsort
Beim Insertionsort werden die Daten von vorne nach hinten durchlaufen. Das aktuelle Element wird betrachtet und anschließend so lange nach links verschoben, bis es an seiner richtigen Position angelangt ist, also der Wert links von ihm nicht mehr größer ist als es selbst. Die Datenmenge lässt sich demnach immer in einen sortieren und einen unsortieren Bereich unterteilen. Das erste Element des unsortieren Bereichs wird an der richtigen Stelle in den sortierten Bereich eingefügt. Deswegen der Name "insertionsort".

public static void insertionsort(){ for(int i = 1; i < daten.length; i++) { int einzufuegen = daten[i]; //Der Wert, der einsortiert werden soll int index = i; //Die Stelle, an der er steht //Verschiebe alle Daten, die weiter hinten als der einzufuegende Wert sind while(index > 0 && einzufuegen < daten[index-1]) { daten[index] = daten[index-1]; index--; } daten[index] = einzufuegen; //Speicher den Wert an der neuen Position } }

Hier ein Demo-Programm, dass ein Integerfeld mit 15 Elementen sortiert: Insertionsort.java

Selectionsort

Struktogramm Selectionsort
Beim Selectionsort wird die zu sortierende Datenmenge in einen sortierten und einen unsortierten Bereich eingeteilt. Der sortierte Bereich befindet sich "links" der unsortierte "rechts". Es wird nun das kleinste Element des unsortierten Bereichs gesucht und an den sortierten Bereich angehängt. Dieser Vorgang wird so lange wiederholt, bis alle Elemente sortiert sind. Man durchsucht demnach immer den unsortierten Bereich nach dem passenden Element, weshalb dieser Algorithmus Selectionsort heißt.

public static void selectionsort(){ for(int i = 0; i < daten.length-1; i++) { int minIndex = i; //Suche den kleinsten Wert im Feld for(int j = i + 1; j < daten.length; j++) { if(daten[j] < daten[minIndex]) { //Kleinerer Wert gefunden minIndex = j; } } //Vertausche das aktuelle Element mit dem kleinsten des unsortierten Bereichs int sicherung = daten[i]; daten[i] = daten[minIndex]; daten[minIndex] = sicherung; } }

Hier ein Demo-Programm, dass ein Integerfeld mit 15 Elementen sortiert: Selectionsort.java

Bubblesort

Struktogramm Bubblesort
Beim Bubblesort werden immer zwei benachbarte Werte verglichen und, wenn der linke größer ist als der rechte, vertauscht. Geht man mit diesem Verfahren von links nach rechts durch eine unsortierte Datenmenge, ist nach einem Durchlauf der größte Wert ganz rechts alles davor ist noch unsortiert. Indem man obriges Prinzip so lange auf den unsortierten Bereich anwendet, wie es Daten gibt, wird die gesamte Menge sortiert. Es werden immer nur die beiden direkt benachbarten Werte verglichen. Man kann sich also eine Blase um dieses Paar vorstellen, das betrachtet wird. Somit entsteht der Name Bubblesort.

public static void bubblesort(){ int n = daten.length; //Stellt dar, bis wohin der unsortierte Bereich geht do{ int nNeu = 1; //Gehe davon aus, dass man fertig ist //Durchlaufe unsortierten Bereich; //i < n-1, da immer mit Partner rechts getauscht wird. //Bei i = n ist der rechte Partner nicht vorhanden for(int i = 0; i < n-1; i++) { if(daten[i] > daten[i+1]) { //Tauschbedarf int sicherung = daten[i]; daten[i] = daten[i+1]; daten[i+1] = sicherung; nNeu = i+1; //Grenze unsortierter Bereich; +1, da i = Index und n = Elementeanzahl } } n = nNeu;//Bis wohin muss ich arbeiten? } while(n > 1); //Solange noch etwas zu tun ist wdh. Schleife }

Hier ein Demo-Programm, dass ein Integerfeld mit 15 Elementen sortiert: Bubblesort.java

Quicksort

Struktogramm Quicksort
Beim Quicksort wird auf das Prinzip der Rekursion zurückgegriffen. Man teilt die zu sortierende Datenmenge immer weiter auf und sortiert immer die kleinereren Teile, indem man ein Element, dass größer ist, mit einem Element das kleiner ist als ein zuvor bestimmtes Teilelement tauscht. Konkret bedeutet dies, dass man die zu sortierende Datenmenge zunächst in der Mitte halbiert. Das Elemet an dieser Stelle wird im Folgenden als Teilelement bezeichnet. Man geht nun vom Anfang der Datenmenge bis zu diesem Element und sucht nach einem, welches größer als das Teilelement ist. Anschließend wird vom Ende der Datenmenge bis zu dem Teilelement ein Element gesucht welches kleiner als dieses ist. Die beiden, auf diesem Weg gefundenen Elemente werden vertauscht. Dies macht man so lange, bis links vom Teilelement nurnoch Daten mit einem kleineren Wert und rechts nur noch Daten mit einem größeren Wert sind. Nun folgt ein rekursiver Aufruf für die beiden Teile (links vom Teilelement und rechts davon). Auch diese werden immer weiter geteilt, bis die gesamte Datenmenge sortiert ist. Aufgrund seiner, durch den rekursiven Aufruf ermöglichten, schnellen Laufzeit trägt dieser Algorithmus den Namen Quicksort.

public static void quicksort() { quicksort(0, daten.length-1); } public static void quicksort(int von, int bis) { if(von < bis) { //Abbruchbedingung int i1 = von; int i2 = bis; int teilstelle = (i1 + i2) / 2; int teilelement = daten[teilstelle]; while(i1 < i2) { //Alle Elemente kleiner als teilelement links die anderen rechts while(daten[i1] <= teilelement && i1 < teilstelle) ++i1; while(daten[i2] >= teilelement && i2 > teilstelle) --i2; if(i1 < i2) { //Vertauschen int hilfe = daten[i1]; daten[i1] = daten[i2]; daten[i2] = hilfe; if(teilstelle == i1) { teilstelle = i2; } if(teilstelle == i2) { teilstelle = i1; } } } //rekursiver Aufruf quicksort(von, teilstelle-1); quicksort(teilstelle+1, bis); } }

Hier ein Demo-Programm, dass ein Integerfeld mit 15 Elementen sortiert: Quicksort.java