-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
40 lines (34 loc) · 853 Bytes
/
QuickSort.java
File metadata and controls
40 lines (34 loc) · 853 Bytes
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
public class QuickSort {
public void quickSort(int[] arr, int low, int high) {
if(low >= high){
return ;
}
int mid = partion(arr, low, high);
quickSort(arr, low, mid - 1);
quickSort(arr, mid + 1, high);
}
private int partion(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low, j = high + 1;
while (true) {
while (less(arr[++i], pivot)) if (i == high) break;
while (less(pivot, arr[--j])) if (j == low) break;
// check if pointers cross
if (i >= j) break;
exch(arr, i, j);
}
// put partitioning item v at a[j]
exch(arr, low, j);
// now, a[low .. j-1] <= a[j] <= a[j+1 .. high]
return j;
}
private boolean less(int v, int w) {
return v < w ? true : false;
}
// exchange a[i] and a[j]
private void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}