package runnerdev;
import java.util.Arrays;
import java.util.List;
public class QuickSort {
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));
SortUtils.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 (SortUtils.less(array[left], pivot)) {
++left;
}
while (SortUtils.less(pivot, array[right])) {
--right;
}
if (left <= right) {
SortUtils.swap(array, left, right);
++left;
--right;
}
}
return left;
}
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);
System.out.print("Integer Array Sorting: ");
// Output
=> 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
for (Integer sort : array) {
System.out.print(sort+" ");
}
String[]
stringArray = { "c", "a", "e", "b", "d" };
quickSort.sort(stringArray);
//SortUtils.print(stringArray);
System.out.print("
String Array Sorting: ");
// Output
=> a b c d e
for (String sort : stringArray) {
System.out.print(sort+" ");
}
}
}
class SortUtils {
/**
*
Helper method for swapping places in array
*
* @param array The array which elements we
want to swap
* @param idx index of the first element
* @param idy index of the second element
*/
static <T> boolean swap(T[] array, int idx, int idy) {
T swap = array[idx];
array[idx] = array[idy];
array[idy] = swap;
return true;
}
/**
*
This method checks if first element is less than the other element
*
* @param v first element
* @param w second element
* @return true if the first
element is less than the second element
*/
static <T extends Comparable<T>> boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
/**
*
This method checks if first element is greater than the other element
*
* @param v first element
* @param w second element
* @return true if the first
element is greater than the second element
*/
static <T extends Comparable<T>> boolean greater(T v, T w) {
return v.compareTo(w) > 0;
}
/**
*
Prints a list
*
* @param toPrint - a list which should be printed
*/
static void print(List<?> toPrint) {
toPrint.stream().map(Object::toString).map(str -> str + " ").forEach(System.out::print);
System.out.println();
}
/**
*
Prints an array
*
* @param toPrint - an array which should be printed
*/
static void print(Object[] toPrint) {
System.out.println(Arrays.toString(toPrint));
}
/**
*
Swaps all position from {@param left} to @{@param right} for {@param array}
*
* @param array is an array
* @param left is a left flip border of the array
* @param right is a right flip border of
the array
*/
static <T extends Comparable<T>> void flip(T[] array, int left, int right) {
while (left <= right) {
swap(array, left++, right--);
}
}
}