Sortieren
Das Sortieren ist ein Standardproblem der Informatik.
Inhaltsverzeichnis
Sortieralgoritmen
Bubblesort
Das Bubblesort-Sortierverfahren versucht in jeder Iteration das größte Element an das Ende des Feldes zu bewegen. Somit besteht das Ende des Feldes immer aus einem sortierten Teilfeld. Nach n Durchläufen ist damit das Feld vollständig sortiert. Bei diesem Verfahren wird in jedem Schritt jedes Element mindestens ein Mal mit einem anderen verglichen.
public static void bubbleSort(int[] A){
for( int n = A.length; n > 1; n--) {
for (int i = 0; i < n-1; i++) {
if (A[i] > A[i+1]){
int swap = A[i];
A[i] = A[i+1];
A[i+1] = swap;
}
}
}
Beispiel: [5, 4, 1, 8, 0, 2, 6, 9, 7, 3]
[4,5, 1, 8, 0, 2, 6, 9, 7, 3] [4, 1, 5, 8, 0, 2, 6, 9, 7, 3] [4, 1, 5, 0, 8, 2, 6, 9, 7, 3] [4, 1, 5, 0, 2, 8, 6, 9, 7, 3] [4, 1, 5, 0, 2, 6, 8, 9, 7, 3] [4, 1, 5, 0, 2, 6, 8, 7, 9, 3] [4, 1, 5, 0, 2, 6, 8, 7, 3, 9] [1, 4, 5, 0, 2, 6, 8, 7, 3, 9] [1, 4, 0, 5, 2, 6, 8, 7, 3, 9] [1, 4, 0, 2, 5, 6, 8, 7, 3, 9] [1, 4, 0, 2, 5, 6, 7, 8, 3, 9] [1, 4, 0, 2, 5, 6, 7, 3, 8, 9] [1, 0, 4, 2, 5, 6, 7, 3, 8, 9] [1, 0, 2, 4, 5, 6, 7, 3, 8, 9] [1, 0, 2, 4, 5, 6, 3, 7, 8, 9] [0, 1, 2, 4, 5, 6, 3, 7, 8, 9] [0, 1, 2, 4, 5, 3, 6, 7, 8, 9] [0, 1, 2, 4, 3, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Heapsort
Im Heapsort wird sich die Eigenschaft zu Nutze gemacht, dass in einem korrekten Heap das kleinste Element immer in der Wurzel des Heaps steht. Wird dieses entfernt und im neuen Baum die Heapstruktur wiederhergestellt, lässt sich das Feld sortieren. Das Wiederherstellen eines Heaps geht relativ schnell.
public static void heapSort(int[] a) {
generateMaxHeap(a);
for( int i = a.length - 1; i > 0; i--) {
tausche(a, 0, i);
heapify(a, 0, i-1);
}
}
private static void generateMaxHeap(int[] a) {
for(int i = (a.length / 2); i >= 0; i--) {
heapify(a, i, a.length-1);
}
}
private static void heapify(int[] a, int aktKnoten, int anzahlKnoten) {
int lsNr = 2*aktKnoten+1, //Nummer des linken Sohns
rsNr = lsNr+1, //Nummer des rechten Sohns
selSohn; //Nummer des selektierten Sohns
if (lsNr <= anzahlKnoten && rsNr > anzahlKnoten) { //es gibt keinen rechten Sohn
if (a[lsNr] < a[aktKnoten]) {
tausche(a, lsNr, aktKnoten);
}
}
else {
if (rsNr <= anzahlKnoten) {
selSohn = (a[lsNr] < a[rsNr] ? lsNr : rsNr);
// Wähle den Sohn mit der kleineren Markierung aus.
// Bei Gleichheit wähle den rechten Sohn.
if (a[selSohn] < a[aktKnoten]) { //Heap-Bedingung verletzt
tausche(a, aktKnoten, selSohn);
heapify(a, selSohn, anzahlKnoten);
}
}
}
}
private static void tausche(int[] a, int i, int j){
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
Insertionsort
Beim Insertionsort (Einfügesortieren) wird versucht, ein Element in der passenden Stelle eines bereits sortierten Teilfeldes einzufügen und den Rest des Feldes dabei zu "verschieben". Da dieses Verfahren bei Feldern viel Aufwand während der Verschiebung erfordert, bieten sich Listen zur Implementierung hier besser an. Damit kann das Einfügen an eine gewisse Position viel einfacher erfolgen.
public static void Insertionsort(int[] A) {
for (int i = 0; i < A.length-1; i++){
for (int j = i+1; j < A.length; j++){
if (A[i] > A[j]){
int swap = A[i];
A[i] = A[j];
A[j] = A[i];
}
}
}
}
Beispiel:
Mergesort
Mergesort ist das klassische Beispiel eines Teile und herrsche-Algorithmus.
public static void Mergesort(int[] a){
int[] hilfsarr = new int[a.length];
doMergesort(a, hilfsarr, 0, a.length-1);
}
private static void doMergesort(int[] a, int[] hilfsarr, int links, int rechts){
// Überprüfung, ob der linke Index kleiner als der rechte Index ist, ansonsten ist das Array sortiert
if ( links < rechts){
// Emittlung des Index des Elements, welches die Mitte ist
int mitte = links + (rechts - links) / 2;
// Sortiere die linke Hälfte
doMergesort(a, hilfsarr, links, mitte);
// Sortiere die rechts Hälfte
doMergesort(a, hilfsarr, mitte + 1, rechts);
// "Verschmelze" (engl. merge) die beiden sortierten Hälten
merge(a, hilfsarr, links, mitte, rechts);
}
}
private static void merge(int[] a, int[] hilfsarr, int links, int mitte, int rechts){
// Kopiere linke und rechte Hälfte in ein Hilfsarray
for (int i = links; i <= rechts; i++){
hilfsarr[i] = a[i];
}
int i = links;
int j = mitte + 1;
int k = links;
// Kopiere die kleinsten Werte entweder von der linken Seite oder vom der rechten Seite zurück in das Ursprungsarray
while (i <= mitte && j <= rechts) {
if (hilfsarr[i] <= hilfsarr[j]){
a[k] = hilfsarr[i];
i++;
}
else {
a[k] = hilfsarr[j];
j++;
}
k++;
}
// Kopiere den Rest der linken Seite in das Ursprungsarray
while (i <= mitte){
a[k] = hilfsarr[i];
k++;
i++;
}
}
Quicksort
Quicksort ist das zweite übliche Beispiel für Teile und Herrsche-Sortieralgorithmen. In ihm wird anhand eines arbiträr (willkürlich) gewählten Wertes (meistens das mittlere) das Feld vorsortiert: Alle Elemente kleiner als das gewählte Element werden links davon einsortiert, alle größeren rechts davon. Damit hat man zwei Teilfelder, die selbst nicht sortiert sind. Also wird rekursiv nach demselben Muster vorgegangen: Die beiden kleineren Teilfelder werden wieder arbiträr nach einem Element aufgeteilt und in zwei grob sortierte Teilstrukturen aufgeteilt. Dies geschieht so lange, bis das Feld in Teilfelder der Größe 1 aufgeteilt wurde. Diese sind alle sortiert, somit auch die größeren Teilfelder und damit das ganze Feld.
public static void quicksort(int[] arr, int links, int rechts) {
if (arr == null || arr.length == 0) {
return;
}
if (links >= rechts) {
return;
}
int mitte = links + (rechts - links) / 2;
int pivot = arr[middle];
int i = links, j = rechts;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int swap = arr[i];
arr[i] = arr[j];
arr[j] = swap;
i++;
j--;
}
}
if (links < j){
quickSort(arr, low, j);
}
if (rechts > i){
quickSort(arr, i, rechts);
}
}
