Sorting 1 million integers from 1 to 9 using Java code
Given a set of 1 million integers from 1 to 9. How would you sort them efficiently?
Input: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]
Output: [1,2,2,3,4,4,5,5,5,6,6,7,8,8,9]
For large inputs Java Collections.sort()
uses TimSort which runs in O (n log (n)) . If you want it to run faster, let's say linear time than you should use a comparison based sorting algorithm.
Since your range of integers is much less than the number of items to sort, this is an ideal use for Counting Sort .
Be k = 9
(range 1 to 9) and N = 1 million
. Your running time will be O (k + N) .
create 10 arrays (or an array of 10 arrays), one for each number, iterate over your input array, and add each number to the corresponding array. finally concatenate all arrays.
Login: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]
Output: [1,2,2,3,4,4,5, 5,5,6,6,7,8,8,9]
This can be solved in O (n) time with O (k) space.
Since the given range is 9, we can create a 9 + 1 array, where each index will store an occurrence of a number in the input array
TempArray = [0 1 2 1 2 3 2 1 2 1] Index 0 1 2 3 4 5 6 7 8 9
All you have to do is read the tempArray and fill the data back into the input.
The value at index 1 is 1, so we'll only add one item.
the value at index 2 is 2, so we'll add two times two.
the value at index 3 is 1, so we'll only add three once.
the value at index 4 is 2, so we'll only add four two times ...
this way you can override the original array.
T (O (n)) S (O (k))
Let me know if you have any confusion.
here is the C # code for the same:
int[] input = new int[15] { 1, 2, 5, 4, 7, 8, 9, 6, 5, 4, 2, 3, 6, 5, 8 };
int k = 9;
int[] temp = new int[k + 1];
for (int index = 0; index < input.Length; index++)
{
temp[input[index]]++;
}
int i = 0; // used for input index
for (int index = 0; index < temp.Length; index++)
{
while (temp[index]-- != 0) // redusing count value after updating the index into input array
input[i++] = index;
}
for (int index = 0; index < input.Length; index++)
{
Console.Write(" {0} ", input[index]);
}