View Javadoc
1   package ch.hslu.exercises.sw14;
2   
3   
4   public class Sort {
5   
6       public static void insertionSort(final int[] a) {
7           int elt;
8           int j;
9           Thread thread = new Thread();
10          for (int i = 1; i < a.length; i++) {
11              elt = a[i]; // next elt for insert
12              j = i; // a[0]..a[j-1] already sorted
13              while ((j > 0) && (a[j - 1] > elt)) {
14                  a[j] = a[j - 1]; // shift right
15                  j--; // go further left
16              }
17              a[j] = elt; // insert elt
18          } // a[0]...a[j] sorted
19      }
20  
21      public static void insertionSort2(final int[] a) {
22          int elt;
23          int j;
24          for (int i = 2; i < a.length; i++) {
25              elt = a[i]; // next elt for insert
26              a[0] = elt; // dummy-element
27              j = i; // a[1]..a[j-1] already sorted
28              while (a[j - 1] > elt) {
29                  a[j] = a[j - 1]; // shift right
30                  j--; // go further left
31              }
32              a[j] = elt; // insert elt
33          } // a[1]...a[j] sorted
34      }
35  
36      public static void quickSort(final char[] a, final int left, final int right) {
37          int up = left; // linke Grenze
38          int down = right - 1; // rechte Grenze (ohne Trennelement)
39          char t = a[right]; // rechtes Element als Trennelement
40          boolean allChecked = false;
41          do {
42              while (a[up] < t) {
43                  up++; // suche grösseres (>=) Element von links an
44              }
45              while ((a[down] >= t) && (down > up)) {
46                  down--; // suche echt kleineres (<) Element von rechts an
47              }
48              if (down > up) { // solange keine Überschneidung
49                  exchange(a, up, down);
50                  up++;
51                  down--; // linke und rechte Grenze verschieben
52              } else {
53                  allChecked = true; // Austauschen beendet
54              }
55          } while (!allChecked);
56          exchange(a, up, right); // Trennelement an endgültige Position (a[up])
57          if (left < (up - 1)) quickSort(a, left, (up - 1)); // linke Hälfte
58          if ((up + 1) < right) quickSort(a, (up + 1), right); // rechte Hälfte, ohne T’Elt.
59      }
60  
61      private static void exchange(final char[] a, final int firstIndex, final int secondIndex) {
62          char tmp;
63          tmp = a[firstIndex];
64          a[firstIndex] = a[secondIndex];
65          a[secondIndex] = tmp;
66      }
67  
68      public static void selectionSort(final int[] a) {
69          for (int i = 0; i < (a.length - 1); i++) {
70              int index = i;
71              for (int j = i + 1; j < a.length; j++) {
72                  if (a[j] < a[index]) {
73                      index = j;
74                  }
75              }
76              int temp = a[i];
77              a[i] = a[index];
78              a[index] = temp;
79          }
80      }
81  
82      static void bubbleSort(int[] arr) {
83          int temp = 0;
84          for (int i = 0; i < arr.length; i++) {
85              for (int j = 1; j < (arr.length - i); j++) {
86                  if (arr[j - 1] > arr[j]) {
87                      //swap elements
88                      temp = arr[j - 1];
89                      arr[j - 1] = arr[j];
90                      arr[j] = temp;
91                  }
92  
93              }
94          }
95      }
96  
97      private static char[] b;
98  
99      public static void mergeSort(final char[] a) {
100         b = new char[a.length]; // zusätzlicher Speicher fürs Mergen
101         mergeSort(a, 0, a.length - 1);
102     }
103 
104     private static void mergeSort(final char a[], final int left, final int right) {
105         int i, j, k, m;
106         if (right > left) {
107             m = (right + left) / 2; // Mitte ermitteln
108             mergeSort(a, left, m); // linke Hälfte sortieren
109             mergeSort(a, m + 1, right); // rechte Hälfte sortieren
110             // "Mergen"
111             for (i = left; i <= m; i++) { // linke Hälfte in Hilfsarray kopieren
112                 b[i] = a[i];
113             }
114             for (j = m; j < right; j++) { // rechte Hälfte umgekehrt in Hilfsa. kopieren
115                 b[right + m - j] = a[j + 1];
116             }
117             i = left;
118             j = right; // Index für linke und rechte Hälfte
119             for (k = left; k <= right; k++) { // füge sortiert in a ein
120                 if (b[i] <= b[j]) {
121                     a[k] = b[i];
122                     i++;
123                 } else {
124                     a[k] = b[j];
125                     j--;
126                 }
127             }
128         }
129     }
130 
131 }
132 
133