-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathQuickSort.java
More file actions
101 lines (84 loc) · 2.73 KB
/
QuickSort.java
File metadata and controls
101 lines (84 loc) · 2.73 KB
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
91
92
93
94
95
96
97
98
99
100
101
/**
* This program QuickSorts an int array.
* Created by Devang on 08-Jan-17.
*/
public class QuickSort {
public static void main(String[] args){
int[] collection = {5, 8, 24, 15, 200, 192, 86, 35, 78, 24 ,9, 24};
printArray(collection);
sort(collection, 0, collection.length - 1);
printArray(collection);
}
private static void sort(int[] collection, int left, int right){
//Base case
if(right - left < 1){
return;
}
//Select pivot
int p = findPivot(collection, left, right);
int pivot = collection[p];
//Swap pivot with left
int t1 = collection[left];
collection[left] = collection[p];
collection[p] = t1;
left++;
// Iterate
int l = left;
int r = right;
while(l <= r) {
while (collection[l] <= pivot && l < right) {
l++;
}
while (collection[r] > pivot && r > left) {
r--;
}
if(l <= r){
//swap values of left and right
int temp = collection[l];
collection[l] = collection[r];
collection[r] = temp;
l++;
r--;
}
}
// swap left and pivot values in array
int t = collection[left - 1];
collection[left - 1] = collection[l-1];
collection[l-1] = t;
p = l - 1;
// recurse for left, pivot - 1
sort(collection, left - 1, p - 1);
// recurse for pivot + 1, right
sort(collection, p + 1, right);
}
private static int findPivot(int[] collection, int left, int right){
int pivot;
if(left == right || right - left == 1){
if(collection[right] > collection[left]) {
pivot = right;
} else {
pivot = left;
}
} else {
int middle = (left + right) / 2;
pivot = median(collection, left, right, middle);
}
return pivot;
}
private static int median(int[] collection, int left, int right, int middle){
int a = collection[left];
int b = collection[right];
int c = collection[middle];
if((a <= b && a >= c) ||(a >= b && a <= c))
return left;
if((b <= a && b >= c) ||(b >= a && b <= c))
return right;
return middle;
}
private static void printArray(int[] collection){
for(int i : collection){
System.out.print("\t" + i);
}
System.out.println();
}
}