Sortieren

Das Sortieren ist ein Standardproblem der Informatik

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 insbesondere vollständig sortiert. Jedoch wird bei diesem Verfahren in jedem Schritt jedes Element mindestens ein mal mit einem anderen verglichen.

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;
        }
    }
}

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 dabei relativ schnell.

public static void heapSort(int[] a) {
       generateMaxHeap(a);
       for( int i = a.length - 1; i > 0; i--) {
           tausche(a, i, 0);
           heapify(a, 0, i);
       }
}

public static void generateMaxHeap(int[] a) {
       for(int i = (a.length / 2) - 1; i >= 0; i--) {
          heapify(a, i, a.length);
       }
}

public staitc void heapify(int[] a, int k, int anzahlKnoten) {
       int lsNR = 2*k,    //Nummer des linken Sohns
           rsNR = 2*k+1,  //Nummer des rechten Sohns
           selSohn;       //Nummer des selektierten Sohns

       if (lsNr <= anzahlKnoten && rsNr > anzahlKnoten) { //es gibt keinen rechten Sohn
           if (heapFeld[lsNr] < heapFeld[k] {
               tausche(a, k, lsNr);
           }
       }
       else if (rsNr <= anzahlKnoten) {
            selSohn = (heapFeld[lsNr] < heapFeld[rsNr] ? lsNr : rsNr);
            // Wähle den Sohn mit der kleineren Markierung aus.
            // Bei Gleichheit wähle den rechten Sohn.

            if (heapFeld[selSohn] < heapFeld[k]) {  //Heap-Bedingung verletzt
                tausche(a, k, selSohn);
                heapify(a, selSohn, anzahlKnoten);
            }
       }
}


public static void tausche(int[] a, int i, int j){
       int swap = a[i];
       a[i] = a[j];
       a[j] = swap;
}

Insertionsort

Insertionsort(int[] A)
for (int i = 1; i < A.length; i++){
    int insort = A[i];
    int j = i;
    while (j > 1 && A[i-j] > insort){
          A[j] = A[j-1];
          j--;
          }
    A[j] = insort;
}

Mergesort

Mergesort ist das klassische Beispiel eines Teile und Herrsche Algorithmus. In ihm wird jedes Teilfeld zuerst in zwei grob sortierte Teilfelder aufgeteilt: Eines mit allen Elementen kleiner als ein arbiträr gewählter Wert (genannt: Pivot) und eines mit allen Elementen größer als dieser. Diese grob sortierten Teilfelder werden anschließend nach dem selben Verfahren sortiert, so lange, bis ein kleinstes Teilfeld als "sortiert" betrachtet werden kann (Ein Feld mit nur einem Element ist sortiert). Anschließend werden die Elemente der sortierten Teilfelder miteinander verschachtelt um ein größeres sortiertes Feld zu erhalten. Dies geht, da die Teilfelder bereits sortiert sind, sehr schnell. Dies wird dann so lange wieder auf das größere Feld angewendet, bis das gesamte Feld sortiert ist.

public static void sort(int[] a){
       if( a.length > 1) {
          int mitte = arry.length / 2;

          int[] links = new int[mitte];
          for (int i = 0; i <= links.length - 1; i++) {
               links[i] = a[i];
          }

          int[] rechts = new int[a.length - mitte];
          for (int i = mitte; i <= a.length - 1; i++) {
               rechts[i - mitte] = a[i];
          }

          sort(links);
          sort(rechts);

          a = merge(links, rechts);
       }
}

public static int[] merge(int[] links, int[] rechts){
       int[] ErgArray = new int[links.length + rechts.length];
       int indexLinks = 0,
           indexRechts = 0,
           indexErg = 0;

       while (indexLinks < links.length && indexRechts < rechts.length) {
             if (links[indexLinks] < rechts[indexRechts]) {
                 ErgArray[indexErg] = links[indexLinks];
                 indexLinks++;
             } else {
                   ErgArray[indexErg] = rechts[indexRechts];
                   indexRechts++;
             }
             indexErg++;
       }

       while (indexLinks < links.length) {
             ErgArray[indexerg] = rechts[indexRechts];
             indexRechts++;
             indexErg++;
       }

       while (indexRechts < rechts.length) {
             ErgArray[indexErg] = rechts[indexRechts];
             indexRechts++;
             indexErg++;
       }

       return ErgArray;
}

Quicksort

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);
       }
}