Friday 21 February 2014

Counting Sort in java

Background

 Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 8:03 PM
 */
public class CountingSort {


    public int[] sort(int[] array) {

        int maxValue = getMaxValue(array);
        return countingSort(array,maxValue);

    }

    public int[] countingSort(int[] input, int maxValue){

        int[] countArray = new int[maxValue+1];
        for(int no : input){
            countArray[no] = countArray[no] + 1;
        }

        for(int i=1;i<countArray.length;i++){
            countArray[i] = countArray[i] + countArray[i-1];
        }

        int[] output = new int[input.length];

        for(int i=output.length-1;i>=0;i--){

            output[countArray[input[i]]-1] = input[i];
            countArray[input[i]] = countArray[input[i]] -1;

        }

        return output;

    }


    private int getMaxValue(int[] array){

        int maxValue = Integer.MIN_VALUE;
        for(int no : array){
            if(no > maxValue){
                maxValue = no;
            }
        }
        return maxValue;
    }


    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        System.out.println("Array after Sort : " + Arrays.toString(new CountingSort().sort(array)));

    }

}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


 NOTE : The modified count array indicates the position of each object in the output sequence.


Time Complexity

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space:
O(n+k)

Related Links

No comments:

Post a Comment

t> UA-39527780-1 back to top