/
DualPivotQuickSort.java
106 lines (90 loc) · 3.14 KB
/
DualPivotQuickSort.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
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
99
100
101
102
103
104
105
106
package com.thealgorithms.sorts;
/**
* Dual Pivot Quick Sort Algorithm
*
* @author Debasish Biswas (https://github.com/debasishbsws) *
* @see SortAlgorithm
*/
public class DualPivotQuickSort implements SortAlgorithm {
/**
* This method implements the Dual pivot Quick Sort
*
* @param array The array to be sorted Sorts the array in increasing order
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
dualPivotQuicksort(array, 0, array.length - 1);
return array;
}
/**
* The sorting process
*
* @param left The first index of an array
* @param right The last index of an array
* @param array The array to be sorted
*/
private static <T extends Comparable<T>> void dualPivotQuicksort(T[] array, int left, int right) {
if (left < right) {
int[] pivots = partition(array, left, right);
dualPivotQuicksort(array, left, pivots[0] - 1);
dualPivotQuicksort(array, pivots[0] + 1, pivots[1] - 1);
dualPivotQuicksort(array, pivots[1] + 1, right);
}
}
/**
* This method finds the partition indices for an array
*
* @param array The array to be sorted
* @param left The first index of an array
* @param right The last index of an array Finds the partition index of an array
*/
private static <T extends Comparable<T>> int[] partition(T[] array, int left, int right) {
if (array[left].compareTo(array[right]) > 0) swap(array, left, right);
T pivot1 = array[left];
T pivot2 = array[right];
int j = left + 1;
int less = left + 1;
int great = right - 1;
while (less <= great) {
// If element is less than pivot1
if (array[less].compareTo(pivot1) < 0) {
swap(array, less, left++);
}
// If element is greater or equal to pivot2
else if (array[less].compareTo(pivot2) >= 0) {
while (less < great && array[great].compareTo(pivot2) > 0) great--;
swap(array, less, great--);
if (array[less].compareTo(pivot1) < 0) swap(array, less, left++);
}
less++;
}
j--;
great++;
// Bring the pivots to their appropriate positions
swap(array, left, j);
swap(array, right, great);
// return the pivots' indices
return new int[] {less, great};
}
private static <T extends Comparable<T>> void swap(T[] array, int left, int right) {
T temp = array[left];
array[left] = array[right];
array[right] = temp;
}
/**
* Main method
*
* @param args the command line arguments
*/
public static void main(String[] args) {
Integer[] array = {24, 8, -42, 75, -29, -77, 38, 57};
DualPivotQuickSort dualPivotQuickSort = new DualPivotQuickSort();
dualPivotQuickSort.sort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
/*
* References: https://www.geeksforgeeks.org/dual-pivot-quicksort/
*/
}