sort n integers of range 零~n^2-1 in O(n) time

sort n integers of range 0~n^2-1 in O(n) time

This is one problem introduced in "Introduction to Algorithm".

We can use radix-sort to solve it.

 

package alg;

import java.util.ArrayList;
import java.util.Iterator;

/*
 * This example shows how to use radix sort algorithm to sort N integers in the range of 0 ~ N^2-1.
 */
public class RadixSortExample {

    void sort(int a[], int N){
        int len = a.length;
        
        ArrayList<ArrayList<Integer>> bucket= new ArrayList<ArrayList<Integer>>(N);
        for(int i = 0; i<N;i++){
            bucket.add(new ArrayList<Integer>(len));
        }
        ArrayList<Integer> temp = new ArrayList<Integer>(len);
        
        for(int i = 0; i< len; i++){
            temp.add(new Integer(a[i]));
        }
        for(int i = 0; i<len; i++){
            int digit0 = temp.get(i).intValue() % N;
            bucket.get(digit0).add(temp.get(i));
        }
        temp.clear();
        
        for(int i = 0; i<N; i++){
            Iterator<Integer> it = bucket.get(i).iterator();
            while(it.hasNext()) temp.add(it.next());
        }
        for(int i = 0; i<N;i++){
            bucket.get(i).clear();
        }
        for(int i = 0; i<len; i++){
            int digit1 = temp.get(i).intValue() / N;
            bucket.get(digit1).add(temp.get(i));
        }
        temp.clear();
        for(int i = 0; i<N; i++){
            Iterator<Integer> it = bucket.get(i).iterator();
            while(it.hasNext()) temp.add(it.next());
        }
        Iterator<Integer> it = temp.iterator();
        while(it.hasNext()) System.out.println(it.next());
        
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a []= {63,20,43,15,56,9,1,28};
        RadixSortExample r = new RadixSortExample();
        r.sort(a,8);
    }

}