Clever Geek Handbook

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]
+3


source to share


3 answers


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) .

+8


source


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.



+1


source


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]);
  }
+1


source






More articles:


All Articles