Wednesday 26 March 2014

Sorting algorithm

    So recently, I just thought of a pretty efficient sorting algorithm. Suppose that you have a list of unsorted elements ranging from lets say 1 to 99. A natural first step to sorting these elements would be to look at the number in front of all the elements. Since the most digits you could have in these sets of numbers is 2, you would look at each number divided by a 10 and then converted to integer, and depending on that, a bunch of sublists can be created to hold all the smaller lists with the same first digit (0 for single digit). These sublists are now half sorted and now a sorting pass should be done on all of these sublists but by looking at the number % 10. After doing that, just put all the sublists back together again and there you have a sorted list. This is an O(n) function. First you would need to find the highest amount of digits, then you would start the sorting passes. There is a shortcoming to this algorithm when for example you have a list as follows:

[99999999999999999999999999999999, 1, 2, 3, 4, 5]

    In that case there would be a ridiculous amount of sorting passes going on for each digit that the first number has. Maybe a better idea is to keep track of all the possible digit lengths and then just skip to the next smallest one if there is only one number for a specific digit length.

No comments:

Post a Comment