Sunday, 1 March 2015

Selection sort in java

Selection sort finds the next minimum in array and replaces it with current index element while iterating through the array.
At the end of the loop array gets sorted.

Following program implements Selection sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class SelectionSort {

    int[] arr;

    SelectionSort() {
        arr = new int[] { 5, 3, 1, 2, 9, 8 };
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        SelectionSort obj = new SelectionSort();
        obj.operate();

    }
    
    public void operate(){

        System.out.println("Array before sortings: ");
        printArray();
        selectionSort(arr);

        System.out.println("Sorted array : ");
        printArray();
    }
    
    /**
     * Not a stable sort
     * O(n^2)
     */
    public void selectionSort(int[] arr){
        
        int length=arr.length;
        for(int i=0; i<length; i++){
            //find the next min and swap
            int min=arr[i];
            int index=i;
            for(int j=i+1; j<length; j++ ){
                if(arr[j]<min){
                    min=arr[j];
                    index=j;
                }
            }
        
            if(index!=i){
                int temp=arr[i];
                arr[i]=arr[index];
                arr[index]=temp;
            }
                    
        }
    }

    public void printArray(){
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }
}

Complexity analysis:
Complexity of Selection sort is O(n^2), since array is iterated and for each iteration minimum element is identified.
For the first element n-1 element compared,for second n-2 elements compared and so on.
So total time taken : (n-1)+(n-2)+(n-3)+.....1 = O(n^2) (worst case and best case)