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(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

?

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

Mergesort

?

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 43 44 45 46 47 48 49 50 51 52

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