Sunday, August 22, 2010

Very Very Quick Sort!!

Welcome back!!
This is a cool algorithm for super fast sorting. This algorithm sorts an array of numbers, nos, whose values range from 0 to n, the result is stored in res The size of nos is x
Declare array arr of size n
Initialise arr to 0

Loop from 0 to x using counter c
arr[nos[c]] ++
End loop


Loop from 0 to n using counter c
If arr[c] > 0
Loop from 0 to arr[c] using counter a
res[c+a] = arr[c]
End loop
End if
End loop
This algorithm trades speed for memory usage, and it is impractical to use, if the range of values to be sorted is large. Memory can be saved if the removal of repititions is not an issue. For example if 1, 9, 5, 9, 4, 4, 6, 7 can be sorted as 1, 4, 5, 6, 7, 9, where the repititions of 4 and 9 are removed. In this case one bit for each value is enough, for indicating whether a vlue is present or not.

No comments:

Post a Comment