Aktuelle Version vom 18. Januar 2017, 18:37 Uhr

Das Sortieren ist ein Standardproblem der Informatik.

Sortieralgorithmen

Bubblesort

Das Bubblesort-Sortierverfahren versucht in jeder Iteration das größte Element an das Ende des Arrays zu bewegen. Daher besteht das Ende des Arrays immer aus einem sortierten Teilfeld. Nach n Durchläufen ist das Array 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. Werden dieses wiederholt entfernt und im jeweils neuen Baum die Heap-Eigenschaften wiederhergestellt, lässt sich das Array 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 Arrays dabei zu "verschieben".

Da dieses Verfahren bei Arrays viel Aufwand während der Verschiebung erfordert, bieten sich hier Listen besser zur Implementierung an. Mit Listen 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:

[5, 4, 1, 8, 0, 2, 6, 9, 7, 3]
 
[4, 5, 1, 8, 0, 2, 6, 9, 7, 3]
[1, 5, 4, 8, 0, 2, 6, 9, 7, 3]
[0, 5, 4, 8, 1, 2, 6, 9, 7, 3]
[0, 4, 5, 8, 1, 2, 6, 9, 7, 3]
[0, 1, 5, 8, 4, 2, 6, 9, 7, 3]
[0, 1, 4, 8, 5, 2, 6, 9, 7, 3]
[0, 1, 2, 8, 5, 4, 6, 9, 7, 3]
[0, 1, 2, 5, 8, 4, 6, 9, 7, 3]
[0, 1, 2, 4, 8, 5, 6, 9, 7, 3]
[0, 1, 2, 3, 8, 5, 6, 9, 7, 4]
[0, 1, 2, 3, 5, 8, 6, 9, 7, 4]
[0, 1, 2, 3, 4, 8, 6, 9, 7, 5]
[0, 1, 2, 3, 4, 6, 8, 9, 7, 5]
[0, 1, 2, 3, 4, 5, 8, 9, 7, 6]
[0, 1, 2, 3, 4, 5, 7, 9, 8, 6]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 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]

Mergesort

Der Mergesort ist das klassische Beispiel eines Teile und herrsche-Algorithmus. Das eingegebene Array wird hierbei solange in zwei Hälften geteilt, bis jedes Teilarray nur noch eine einzige Zahl enthält. Danach werden die Teilarrays Schritt für Schritt wieder zusammengesetzt und dabei sortiert, bis am Ende ein einzelnes sortiertes Array vorhanden ist.

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

Beispiel:

[5, 4, 1, 8, 0, 2, 6, 9, 7, 3]

[5, 4, 1, 8, 0] ; [2, 6, 9, 7, 3]
[5, 4] ; [1, 8, 0] ; [2, 6] ; [9, 7, 3]
[5] ; [4] ; [1, 8] ; [0] ; [2] ; [6] ; [9] ; [7, 3]
[5] ; [4] ; [1] ; [8] ; [0] ; [2] ; [6] ; [9]; [7] ; [3]
[4, 5] ; [1, 8] ; [0, 2] ; [6, 9] ; [3, 7]
[1, 4, 5, 8] ; [0, 2, 6, 9] ; [3, 7]
[0, 1, 2, 4, 5, 6, 8, 9] ; [3, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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 Array vorsortiert: Alle Elemente kleiner als das gewählte Element werden links davon einsortiert, alle größeren rechts davon. Damit hat man zwei Teilarrays, die selbst nicht sortiert sind. Also wird rekursiv nach dem gleichen Muster vorgegangen: Die beiden kleineren Teilarrays werden wieder arbiträr nach einem Element aufgeteilt und in zwei grob sortierte Teilstrukturen aufgeteilt. Dies geschieht so lange, bis das Array in Teilarrays der Größe 1 aufgeteilt wurde. Diese sind alle sortiert, somit auch die größeren Teilarrays und damit das gesamte Array.

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