Quick Select Algorithm implementation in Java.

Quickselect: Is an algorithm to find kth smallest or largest element in an unsorted array. More information is here http://en.wikipedia.org/wiki/Quickselect.

The Quickselect algorithm is almost same as Quicksort except we ignore one half in each recursion in Quickselect. Hence, the complexity of Quickselect is definitely lesser than O(n^2). The average complexity would be O(n) with a constant multiplication factor.

Basic idea here is to choose a pivot and alter the array such that all the left elements should be lesser or equal to the pivot and right side elements should be greater than the pivot.

There are much better algorithms to choose the appropriate pivot, but here I am taking the first element as the pivot. After an iteration moving the pivot to the center (its appropriate position).

I have added comments in critical sections of the code.

package com.rp.algos;

import java.util.Arrays;

public class QuickSelect {

    /**
     * @param args
     */
    public static void main(String[] args) {
        QuickSelect q = new QuickSelect();
        q.test();
    }
    
    private void test() {
        int[] test = {45, 34, 78, 3, 7, 14, 24};
        System.out.println("Original Array: \n" + Arrays.toString(test));
        System.out.println("------------------");
        
        int ind;
        ind = quickSelect(test, 0, test.length - 1, 0);
        System.out.println( "1st smallest = " + test[ind]); 
        ind = quickSelect(test, 0, test.length - 1, 1);
        System.out.println( "2nd smallest = " + test[ind]); 
        ind = quickSelect(test, 0, test.length - 1, 2);
        System.out.println( "3rd smallest = " + test[ind]); 
        ind = quickSelect(test, 0, test.length - 1, 6);
        System.out.println( "7th smallest = " + test[ind]); 
        
    }

    private int quickSelect(int[] a, int first, int last, int k) {
        //base case
        if(first >= last) {
            return first;
        }
        //partition the array (re arrange the array) and get the index of pivot
        int pivot = partition(a, first, last);       
        // Here it is different from Quicksort, in quick sort, we need sort both the halves ignoring the pivot (as the pivot is already sorted). 
        // In Quickselect we really interested only in one half and we ignore other half.
        // If k < pivot, our element is in the left portion  
        if(k < pivot) {
            //recursively select the pivot for the left portion
            return quickSelect(a, first, pivot, k);
        } 
        if(k > pivot) {
            return quickSelect(a, pivot+1, last, k);
        }
        return first;
    }

    
    private int partition(int[] a, int first, int last) {
        //define right and left for this recursion to re arrange the elements with in the array (infact right or left portion of the array)
        int left = first, right = last;
        //here taking the first element as the pivot
        int pivot = a[first];
        
        while (left < right) {
            //find an element which is bigger than pivot to push right portion of the array
            while (pivot >= a[left] && left < right) {
                left++;
            }
            
            //find an element from right which is lower than pivot to push it to left portion of the array
            while(pivot < a[right]) {
                right--;
            }
            
            if(left < right) {
                swap(a, left, right);
            }
        }
        //by the time we reach here, 'right' will be the seperator of left and right portion of the array. 
        //From index 1 to right all elements are lesser than the pivot and the index from right+1 to left are the higher than pivot.
        //We need to swap right and pivot to fit the pivot as the separator.
        swap(a, first, right);
        return right;
    }

    private void swap(int[] a, int left, int right) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
}