Sortieren: Unterschied zwischen den Versionen

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

Version vom 30. Dezember 2015, 17:03 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(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;
}

Quicksort

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