QuickSelect.java

public class QuickSelect {
    /*
     * partition function
     * array     : array on which partitioning has to be done
     * left      : left index of the partitioning subarray
     * right     : right index of the partitioning subarray
     * pivotIndex : pivot index from which partition has to done
     * return    : the index of the last element of the left subarray
     */
    private static int partition(int[] array, int left, int right, int pivotIndex) {
        int pivotValue = array[pivotIndex];
        int temp = array[right];
        array[right] = array[pivotIndex];
        array[pivotIndex] = temp;
        int storeIndex = left;
        while (left < right) {
            if (array[left] < pivotValue) {
                temp = array[storeIndex];
                array[storeIndex] = array[left];
                array[left] = temp;
                storeIndex++;
            }
            left++;
        }
        temp = array[right];
        array[right] = array[storeIndex];
        array[storeIndex] = temp;
        return storeIndex;
    }

    /*
     * Quick Select function
     * left        : left index of the subarray
     * right       : right index of the subarray
     * pos         : position to find the element using quick sort
     * return      : the value of element at pos place in the sorted array
     */
    public static int quickSelect(int[] array, int left, int right, int pos) {
        int pivotIndex;
        if(pos < 0 || pos >= array.length) {
            throw new IndexOutOfBoundsException("index: " + pos);
        }
        if (left == right) {
            return array[left];
        }
        pivotIndex = right - 1;
        pivotIndex = partition(array, left, right, pivotIndex);
        if (pos == pivotIndex) {
            return array[pivotIndex];
        }
        else if (pos < pivotIndex) {
            return quickSelect(array, left, pivotIndex - 1, pos);
        }
        else {
            return quickSelect(array, pivotIndex + 1, right, pos);
        }
    }

    public static void main(String[] args) {
        int[] array = {10, 5, 1, 6, 7, 3, 2, 4, 8, 9};
        System.out.println(quickSelect(array, 0, array.length - 1, 3));
    }

}