5 Say that the dierent values in an unsorted array are only

5. Say that the dierent values in an unsorted array are only 10 values (each repeating many times). Give an algorithm to sort the array. Example: in < 1,2,1,3,2,1,3,2,1,3,2,1,2,3 > there are many numbers but only 3 dierent values.

Solution

Answer:

The best algorithm for such cases is the counting algorithm . Which goes like this :

1. Take these elements in the range 0 to 14

Index : 0 1 2 3 4 5 6 7 8 9 10 1 12 13 14

Count: 1 2 1 3 2 1 3 2 1 3 2 1 1 2 3

2. Modify the count such that elements at the index stores the sum of previous.

3. Output the object from the array by decreasing its count by 1 .

It will take O(n) time.