Quick Sort Algorithm

Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved. develop by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a normally used algorithm for sorting. Robert Sedgewick's Ph.D. thesis in 1975 is considered a milestone in the survey of Quicksort where he resolved many open problems associated to the analysis of various pivot choice schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps. 

Jon Bentley and Doug McIlroy integrated various improvements for purpose in programming library, including a technique to deal with equal components and a pivot scheme known as pseudomedian of nine, where a sample of nine components is divided into groups of three and then the median of the three medians from three groups is choose. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library's sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy.
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);
    }
}

LANGUAGE:

DARK MODE: