Sortieren

Das Sortieren ist ein Standardproblem der Informatik

Sortieralgoritmen

Bubblesort

?

1 2 3 4 5 6 7 8 9 10

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

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(k, selSohn);                 heapify(selSohn);             }        } }     public static void tausche(int[] a, int i, int j){        int swap = a[i];        a[i] = a[j];        a[j] = swap; }

Insertionsort

?

1 2 3 4 5 6 7 8 9 10

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