# Given a collection of 1 million integers, all ranging between 1 to 9, how would you sort them in Big O(n) time?

This is a typical Integer Sorting problem with a constraint that the number range to sort is very limited in spite 1 million total entries. Integer Sorting with limited range is achieved efficiently with Bucket Sorting.

From Wikipedia

Bucket sort, counting sort, radix sort, and van Emde Boas tree sorting all work best when the key size is small; for large enough keys, they become slower than comparison sorting algorithm.

Integer Sorting Techniques:

Sorting Algorithms:

## Algorithm Steps

- Create a array of size 9
- At each index store the occurrence count of the respective integers. Doing this will achieve this sorting with time complexity of Big O(n) and even the memory requirements are minimized.
- In Order to print the output just traverse the above created array.

Bucket Sort 0-9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class BucketSort {
public int[] sort(int[] array, int min, int max) {
int range = max - min + 1;
int[] result = new int[range];
for (int i: array) {
result[i]++; **(1)**
}
return result;
}
public void testBucketSortFor1To9() {
int[] array = {
2, 1, 5, 1, 2, 3, 4, 3, 5, 6, 7, 8, 5, 6, 7, 0
};
int[] sort = sort(array, 0, 8);
for (int i = 0; i < sort.length; i++) {
for (int j = 0; j < sort[i]; j++) {
System.out.println(i);
}
}
}
}

- Storing the count of occurence for each number

Program output:

0,1,1,2,2,3,3,4,5,5,5,6,6,7,7,8

## For more such questions, you can get my ebook

Cracking Core Java Interviews v3.4 updated on April 2018

Buy from Pothi.com

## No comments:

## Post a Comment

Your comment will be published after review from moderator