Algorithms/src/sorting_searching/QuickSort.java at main · Flopsey/Algorithms · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
packagesorting_searching;

importjava.util.Comparator;

publicclassQuickSort {

publicstaticvoidmain(String[] args) {
// Example:
int[] array = {91, 34, 86, 39, 27, 87, 70, 48, 100, 95};
quickSort(array);
System.out.println(java.util.Arrays.toString(array)); // [27, 34, 39, 48, 70, 86, 87, 91, 95, 100]
 }

publicstaticvoidquickSort(int[] a) {
quickSort(a, 0, a.length - 1);
 }

privatestaticvoidquickSort(int[] a, intleft, intright) {
if (left >= right) {
return;
 }
intk = partition(a, left, right);
quickSort(a, left, k - 1);
quickSort(a, k + 1, right);
 }

publicstatic <TextendsComparable<? superT>> voidquickSort(T[] a) {
quickSort(a, Comparator.naturalOrder(), 0, a.length - 1);
 }

publicstatic <T> voidquickSort(T[] a, Comparator<T> comp) {
quickSort(a, comp, 0, a.length - 1);
 }

privatestatic <T> voidquickSort(T[] a, Comparator<T> comp, intleft, intright) {
if (left >= right) {
return;
 }
intk = partition(a, comp, left, right);
quickSort(a, comp, left, k - 1);
quickSort(a, comp, k + 1, right);
 }

privatestaticintpartition(int[] a, intleft, intright) {
inti = left;
intj = right - 1;
intpivot = a[right];
do {
while (i < right && a[i] < pivot) {
 ++i;
 }
while (j > left && a[j] > pivot) {
 --j;
 }
if (i < j) {
inttemp = a[i];
a[i] = a[j];
a[j] = temp;
 }
 } while (i < j);
inttemp = a[i];
a[i] = a[right];
a[right] = temp;
returni;
 }

privatestatic <T> intpartition(T[] a, Comparator<T> comp, intleft, intright) {
inti = left;
intj = right - 1;
Tpivot = a[right];
do {
while (i < right && comp.compare(a[i], pivot) < 0) {
 ++i;
 }
while (j > left && comp.compare(a[j], pivot) > 0) {
 --j;
 }
if (i < j) {
Ttemp = a[i];
a[i] = a[j];
a[j] = temp;
 }
 } while (i < j);
Ttemp = a[i];
a[i] = a[right];
a[right] = temp;
returni;
 }

}