-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathQuickSort.java
More file actions
47 lines (38 loc) · 1.17 KB
/
Copy pathQuickSort.java
File metadata and controls
47 lines (38 loc) · 1.17 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
package dev.idion.thinking.sorting;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] arr = {3, 5, 4, 4, 7, 4, 8, 1, 2, 6};
quickSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private int partition(int[] arr, int firstIndex, int lastIndex) {
int pivot = arr[firstIndex];
int k = lastIndex;
for (int j = lastIndex; j > firstIndex; j--) {
if (arr[j] > pivot) {
// swap
int temp = arr[j];
arr[j] = arr[k];
arr[k] = temp;
k--;
}
}
// pivot swap
int temp = arr[firstIndex];
arr[firstIndex] = arr[k];
arr[k] = temp;
return k;
}
public void sort(int[] arr, int firstIndex, int lastIndex) {
if (firstIndex < lastIndex) {
int pi = partition(arr, firstIndex, lastIndex);
sort(arr, firstIndex, pi - 1);
sort(arr, pi + 1, lastIndex);
}
}
public void sort(int[] arr) {
this.sort(arr, 0, arr.length - 1);
}
}