Sortieren: Unterschied zwischen den Versionen

Aus EINI
Wechseln zu: Navigation, Suche
(→‎Heapsort)
Zeile 21: Zeile 21:
 
==Heapsort==
 
==Heapsort==
  
 +
<source lang="java">
 +
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(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;
 +
}
 +
 +
</source>
  
 
==Insertionsort==
 
==Insertionsort==

Version vom 30. Dezember 2015, 16:34 Uhr

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

Mergesort

Quicksort

Von „https://ls14-eini.cs.tu-dortmund.de/index.php?title=Sortieren&oldid=540“