Was ist der schnellste Sortieralgorithmus?

Sortieralgorithmen sind dazu gedacht, eine bestimmte Anzahl von Behältern (zum Beispiel ein Array) zu sortieren. Dazu gibt es verschiedene Methoden. Es gibt verschiedene Algorithmen zum Sortieren, die schnell und effizient sind. Wir wollen einige dieser Algorithmen vorstellen.

Bubble Sort
Bubble Sort ist wohl einer der Einfachsten Algorithmen zum Sortieren, die es gibt. Das Prinzip besteht darin, dass man jedes Feld mit dem nachfolgenden Feld vergleicht. Ist es kleiner, dann wird es getauscht. Ist es größer oder gleich, so wird es so gelassen, wie es ist. Das alles wird solange n-1 mal wiederholt (n ist dabei die Länge des Arrays). Bubble Sort heißt deswegen Bubble Sort, weil die Elemente wie Luftblasen nach hinten fliegen. Der Code sieht folgendermaßen aus:

public static int[] bubblesort(int[] feld) {
		int temp;
		for(int i = 1; i < feld.length; i++) {
			for(int j = 0; j < feld.length - i; j++) { if(feld[j] > feld[j + 1]) {
					temp = feld[j];
					feld[j] = feld[j + 1];
					feld[j + 1] = temp;
				}
				
			}
		}
		return feld;
	}

Insertion Sort
Im Gegensatz zu Bubble Sort wird hierbei das Element an der richtigen Stelle eingefügt. Das heißt, wir durchlaufen das Array und fügen das Element an der richtigen Stelle im neuen Array an.

public static int[] insertionSort(int[] feld) {
		int temp;
		for (int i = 1; i < feld.length; i++) {
			temp = feld[i];
			int j = i;
			while (j > 0 && feld[j - 1] > temp) {
				feld[j] = feld[j - 1];
				j--;
			}
			feld[j] = temp;
		}
		return feld;
}

Quicksort
Quicksort ist wohl der schnellste Algorithmus, den es zur Zeit gibt. Quicksort funktioniert folgendermaßen: Zunächst wird ein Trennelement gewählt. Dies ist häufig das Mittlere. Danach wird das Feld so umgeordnet, dass in der Kette links vom Trennelement die kleinsten Werte und in der Kette rechts vom Trennelement die größten Werte stehen. Nun wird in jeder Teilkette wieder ein Trennelement gewählt und der ganze Vorgang beginnt vom Neuen. Zum Schluss wird alles wieder zusammengesetzt. Der Code sieht folgendermaßen aus:


public class QuickSorter
{
  private int[] a;
  private int n;

  public void sortiere(int[] a)
  {
    this.a = a;
    n = a.length; // Länge berechnen
    quicksort(0, n-1); // Starten
  }

  private void quicksort (int lo, int hi)
  {
    int i = lo, j = hi;

    // Trennelement
    int x= a[lo + (hi-lo) / 2];

    // Aufteilen
    while (i <= j)
    {
      while (a[i] < x) i++; 
      while (a[j] > x) j--;
      if (i<=j)
      {
        swap(i, j);
        i++; j--;
      }
    }

    // Rekursiver Aufruf mit quicksort
    if (lo < j) quicksort(lo, j);
    if (i < hi) quicksort(i, hi);
  }

  private void swap(int i, int j)
  {
    int t=a[i];
    a[i]=a[j];
    a[j]=t;
  }
}

Es gibt noch zahlreiche weitere Sortieralgorithmen. Dazu zählen HeapSort, MergeSort, SelectionSort, etc… Auf Wikipedia gibt es eine Liste mit den häufigsten Sortieralgorithmen.