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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s