**
 * This class represents non comparison based Sorting Methods 
 * Bucket sort and Radix Sort
 */

import java.util.*;

public class NonComparisonSorting
{
	int A[];
	int size;
	public NonComparisonSorting(int size){
		this.size = size;
		Random R = new Random(size);
		A = new int[size];
		for (int i=0;i<size;i++)
			A[i] = Math.abs(R.nextInt(size));
	}
	
	public void bucketSort(){
		//place elements into buckets based on their digits
		ArrayList[] B = new ArrayList[10];
		for (int i=0;i<10;i++)
			B[i] = new ArrayList();
		for (int i=0;i<size;i++)
			B[A[i]/10].add(new Integer(A[i]));
		
		//write the elements back to original array A
		int j=0;
		for (int i=0;i<10;i++){
			Object[] tmp = B[i].toArray();
			for (int k=0;k<tmp.length;k++){
				A[j++] = ((Integer)tmp[k]).intValue();
			}
		}
			
		
	}
	
	/*
	 * This is a specific implementation of Radix sort
	 * that works for integers with two digits. You can 
	 * extend this to more generic types.
	 */
	public void radixSort(){
		// sort by the last digit first
		ArrayList[] B = new ArrayList[10];
		for (int i=0;i<10;i++)
			B[i] = new ArrayList();
		for (int i=0;i<size;i++)
			B[A[i]%10].add(new Integer(A[i]));
		//now sort by first digit. Maintain the stable sort
		// order
		ArrayList[] C = new ArrayList[10];
		for (int i=0;i<10;i++)
			C[i] = new ArrayList();
        for (int j=0;j<10;j++){
        	for (int k=0;k<B[j].size();k++){
        		int n = ((Integer)(B[j].get(k))).intValue();
        		C[n/10].add(new Integer(n));
        	}
        }
        
      //write the elements back to original array A
		int j=0;
		for (int i=0;i<10;i++){
			Object[] tmp = C[i].toArray();
			for (int k=0;k<tmp.length;k++){
				A[j++] = ((Integer)tmp[k]).intValue();
			}
		}
	}
	
	
	
	public String toString(){
		String S="";
		for (int i=0;i<size;i++)
			S += A[i] + " ";
		return S+"\n";
	}