Repository navigation
Expand file tree
/
Copy pathQuickSort.java
More file actions
83 lines (70 loc) · 1.67 KB
/
Copy pathQuickSort.java
File metadata and controls
83 lines (70 loc) · 1.67 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
package practice;
import java.util.*;
public class QuickSort {
public static void main(String[] args) {
int arr[] = { 4, 77, 98, 30, 20, 50, 77, 22, 49, 2 };
int arr4[] = { 1 };
int arr2[] = { 69, 10, 30, 2, 16, 8, 31 };
int arr3[] = { 69, 10, -1, 2, 16, 8, 31 };
quickSort1(arr, 0, arr.length - 1);
// quickSort2(arr2, 0, arr2.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
// for (int i = 0; i < arr2.length; i++) {
// System.out.print(arr2[i] + " ");
// }
}
public static void quickSort1(int[] data, int l, int r) {
int left = l;
int right = r;
int pivot = data[(l + r) / 2];
while(left<=right) {
while (data[left] < pivot) {
left++;
}
while (data[right] > pivot) {
right--;
}
if (left <= right) {
int temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}
}
if (l < right)
quickSort1(data, l, right);
if (r > left)
quickSort1(data, left, r);
}
public static int partition(int arr[], int left, int right) {
int pivot = arr[(left + right) / 2];
while (left <= right) {
while ((arr[left] < pivot)) {
left++;
}
while ((arr[right] > pivot)) {
right--;
}
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return left;
}
public static void quickSort2(int arr[], int left, int right) {
int pivotNewIndex = partition(arr, left, right);
if (left < pivotNewIndex -1) {
quickSort2(arr, left, pivotNewIndex - 1);
}
if (pivotNewIndex < right) {
quickSort2(arr, pivotNewIndex, right);
}
}
}