-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSort.java
73 lines (69 loc) · 2.04 KB
/
QuickSort.java
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package s2.sort;
/**
*
* @author s@sclaingbits.com
*/
public class QuickSort extends Sortierer {
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche das Feld an die
* Oberklasse weiter. Der Algorithmus ist nicht parallel (false Argument)
*
@param s das zu sortierende Feld
*/
public QuickSort(int[] s) {
super(s, false);
}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
*
* @param startIndex Beginn des zu sortierenden Intervalls
* @param endeIndex Ende des zu sortierenden Intervalls
*/
@Override
public void sortieren(int startIndex, int endeIndex) {
int i = startIndex;
int j = endeIndex;
int pivotWert = feld[(startIndex + endeIndex)/2];
//System.out.println("von"+ startIndex+", bis:"+endeIndex +
// " pivot:" + pivotWert);
while (i <= j) {
// Suche vom unteren Ende des Bereichs aufsteigend einen
// Feldeintrag welcher groesser als das Pivotelement ist
while (feld[i] < pivotWert) {
i++;
vglZaehler();
}
// Suche vom oberen Ende des Bereichs absteigend einen
// Feldeintrag der kleiner als das Pivotelement ist
while (feld[j] > pivotWert) {
j--;
vglZaehler();
}
// Vertausche beide Werte falls die Zeiger sich nicht
// aufgrund mangelnden Erfolgs überschnitten haben
if (i <= j) {
tausche(i, j);
i++;
j--;
}
}
// Sortiere unteren Bereich
if (startIndex < j) {
sortieren(startIndex, j);
}
// Sortiere oberen Bereich
if (i < endeIndex) {
sortieren(i, endeIndex);
}
}
/**
* Liefert den Namen des Insertion Sorts
*
* @return Name des Algorithmus
*/
@Override
public String algorithmus() {
return "QuickSort";
}
}