Sortieren: Unterschied zwischen den Versionen

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

Version vom 30. Dezember 2015, 17:20 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

?
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
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);
       }
}
Von „https://ls14-eini.cs.tu-dortmund.de/index.php?title=Sortieren&oldid=545“