/
QuickSort.java
63 lines (53 loc) · 2.54 KB
/
QuickSort.java
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
package com.yunikov.algorithms.sort;
import com.yunikov.algorithms.util.RandomUtils;
import com.yunikov.algorithms.util.ArrayUtils;
/**
* <a href="https://en.wikipedia.org/?title=Quicksort">Quick sort</a> algorithm with randomized pivot point.
* Running time is O(n*log(n)).
*/
public class QuickSort extends Sort {
@Override
protected void doSort(final int[] array) {
quickSort(array, 0, array.length);
}
/**
* Randomly chooses pivot index between start point and the end point.
*
* @param startPoint lowest bound to choose the pivot from
* @param endPoint highest bound to choose the pivot from
* @return pivot index between start point and end point
*/
protected int choosePivotIndex(final int startPoint, final int endPoint) {
if (startPoint == endPoint) {
return startPoint;
}
return RandomUtils.randomInt(startPoint, endPoint);
}
private void quickSort(final int[] array, final int leftIndex, final int rightIndex) {
if (leftIndex < rightIndex) {
final int pivotIndex = choosePivotIndex(leftIndex, rightIndex - 1);
final int newPivotIndex = partition(array, pivotIndex, leftIndex, rightIndex);
quickSort(array, leftIndex, newPivotIndex);
quickSort(array, newPivotIndex + 1, rightIndex);
}
}
private int partition(final int[] array, final int pivotIndex, final int leftIndex, final int rightIndex) {
// put the pivot to the first position of part to be sorted
ArrayUtils.swap(array, leftIndex, pivotIndex);
final int pivot = array[leftIndex];
int partitionedMiddle = leftIndex + 1; // holds the middle point between partitioned elements
// left from partitionedMiddle are less than the pivot, right from partitionedMiddle are bigger than the pivot
for (int currentPosition = leftIndex + 1; currentPosition < rightIndex; currentPosition++) {
// swap only if element is less than the pivot
// otherwise it stays on the right part (where the bigger elements than the pivot are)
if (array[currentPosition] < pivot) {
ArrayUtils.swap(array, currentPosition, partitionedMiddle);
partitionedMiddle++;
}
}
// place the pivot at the partitioned middle
// so elements less than the pivot are left from it, and the ones bigger than the pivot are right from it
ArrayUtils.swap(array, leftIndex, partitionedMiddle - 1);
return partitionedMiddle - 1;
}
}