(radix sort)

Problem Statement

Given an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time.

 

//http://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/public class RadixSort {     public void radixSort(int arr[], int maxDigits){        int exp = 1;//10^0;        for(int i =0; i < maxDigits; i++){            ArrayList bucketList[] = new ArrayList[10];            for(int k=0; k < 10; k++){                bucketList[k] = new ArrayList();            }            for(int j =0; j < arr.length; j++){                int number = (arr[j]/exp)%10;                bucketList[number].add(arr[j]);            }            exp *= 10;            int index =0;            for(int k=0; k < 10; k++){                for(int num: bucketList[k]){                    arr[index] = num;                    index++;                }            }        }         System.out.println("Sorted numbers");        for(int i =0; i < arr.length; i++){            System.out.print(arr[i] +", ");        }    }     public static void main(String[] argv){        int n = 5;        int arr[] = {1,4,2,3,5,10,8};        new RadixSort().radixSort(arr, 2);    }} quicksort to find the nth in liner time.