java/sorting/QuickSort.java at master · rmnbrgr/java · 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
91
92
93
94
95
96
97
98
/**
 * Java implementation of quick sort
 *
 * @author Tibeyev Timur (timurtibeyev@gmail.com)
 */

publicclassQuickSort {

/**
 * Method responsible for sorting array.
 *
 * @param arr array of elements
 * @param left start of the segment to sort
 * @param right end of the segment to sort
 */
privatevoidsort(int[] arr, intleft, intright) {
if (left >= right) {
return;
 }

inti = left;
intj = right;

intmid = (i + j) / 2;
// Pivot element
intv = arr[mid];

while (i < j) {
// Find element from the left side, which is equal or greater than pivot element
while (arr[i] < v) {
i++;
 }

// Find element from the right side, which is equal or less than pivot element
while (v < arr[j]) {
j--;
 }

// If such elements exist, perform swapping
if (i <= j) {
swap(arr, i, j);
i++;
j--;
 }
 }

// Recursively sort left subarray
sort(arr, left, j);
// Recursively sort right subarray
sort(arr, i, right);
 }

/**
 * Swaps two elements.
 *
 * @param arr array of elements
 * @param i first index
 * @param j second index
 */
privatevoidswap(int[] arr, inti, intj) {
intbuf = arr[i];
arr[i] = arr[j];
arr[j] = buf;
 }

/**
 * Entry point, invokes sorting methods and prints resulting array.
 *
 * @param arr array to sort
 */
publicvoidrun(int[] arr) {
sort(arr, 0, arr.length - 1);
printArray(arr);
 }

/**
 * Utility method to print array.
 *
 * @param arr array to print
 */
privatevoidprintArray(int[] arr) {
for (inti : arr) {
System.out.print(i + " ");
 }
System.out.println();
 }

/**
 * {@code Main} method. Initializes {@link QuickSort} object and passes simple
 * array to sort.
 *
 * @param args cmd arguments
 */
publicstaticvoidmain(Stringargs[]) {
intarr[] = { 100, 19, 23, 1, 4, 23, 66 };
newQuickSort().run(arr);
 }
}