Wednesday, December 2, 2015

Key Indexed Counting - Java

Can be used to sort and array of N integers between 0 and R-1.

Complexity - Linear time.

Uses ~11N + 4R array accesses.
Extra space proportional to N+R.

Java Code -

import java.util.Arrays;

public class KeyIndexedCounting {
    public static void main(String[] args){
        int r = 6;
        
        //Can only contain elements 0<=i<=5 as r = 6
        int a[] = {2,3,1,1,1,0,5,1,1,2,3,0};
        int N = a.length;
        
        //Count array to keep track of the number of type of 
        //different elements
        int count[] = new int[r+1];
        
        for(int i=0;i<N;++i){
            count[a[i]+1]++;
        }
        
        for(int i=0;i<r;++i){
            count[i+1] += count[i];
        }
        
        
        int i=0;
        int t=0;
        while(i<N){
            int c = count[t+1]-count[t];
            while(c-->0){a[i++]=t;}
            t++;            
        }
        System.out.println(Arrays.toString(a));
    }
}

Output -

[0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 5]

No comments:

Post a Comment