QuickSort.java
package Sorts;⏎
⏎
import static Sorts.SortUtils.*;⏎
⏎
/**⏎
* @author Varun Upadhyay (https://github.com/varunu28)⏎
* @author Podshivalov Nikita (https://github.com/nikitap492)⏎
* @see SortAlgorithm⏎
*/⏎
class QuickSort implements SortAlgorithm {⏎
⏎
/**⏎
* This method implements the Generic 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) {⏎
doSort(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 doSort(T[] array, int left, int right) {⏎
if (left < right) {⏎
int pivot = randomPartition(array, left, right);⏎
doSort(array, left, pivot - 1);⏎
doSort(array, pivot, right);⏎
}⏎
}⏎
⏎
/**⏎
* Ramdomize the array to avoid the basically ordered sequences⏎
* ⏎
* @param array The array to be sorted⏎
* @param left The first index of an array⏎
* @param right The last index of an array⏎
* @return the partition index of the array⏎
*/⏎
⏎
private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {⏎
int randomIndex = left + (int)(Math.random()*(right - left + 1));⏎
swap(array, randomIndex, right);⏎
return partition(array, left, right);⏎
}⏎
⏎
/**⏎
* This method finds the partition index 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) {⏎
int mid = (left + right) >>> 1;⏎
T pivot = array[mid];⏎
⏎
while (left <= right) {⏎
while (less(array[left], pivot)) {⏎
++left;⏎
}⏎
while (less(pivot, array[right])) {⏎
--right;⏎
}⏎
if (left <= right) {⏎
swap(array, left, right);⏎
++left;⏎
--right;⏎
}⏎
}⏎
return left;⏎
}⏎
⏎
// Driver Program⏎
public static void main(String[] args) {⏎
⏎
// For integer input⏎
Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};⏎
⏎
QuickSort quickSort = new QuickSort();⏎
quickSort.sort(array);⏎
⏎
//Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111⏎
print(array);⏎
⏎
String[] stringArray = {"c", "a", "e", "b", "d"};⏎
quickSort.sort(stringArray);⏎
⏎
//Output => a b c d e⏎
print(stringArray);⏎
}⏎
}⏎
⏎