Sort the array in O(N)

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.

Solution

We can sort the array in O(N) using radix sort, by using a list of lists of size 10, first position denotes the buckets for 0, 10th pos for 9.

We need passes equal to the double of digits in N, as the number of digits in N^2 can be maximum double of the digits in N. To get a digit we can first divide number with 10^i and then get the remainder after dividing by 10, where i = 0 to 2*Number of digits in N. You can understand this better by this radix sort java code snippet below.

Java Code for Radix Sort

import java.util.ArrayList;

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);
	}
}

Facebook Comments