Non-Comparison Based Sorting Algorithms

In the previous lessons we discussed three basic sorting algorithms, bubble sort, insertion sort and selection sort, each of which is easy to implement, but takes O(n2) steps in average case to sort a list of size n. More advanced recursive algorithms like Quick Sort and Merge Sort are hard to implement, but runs more efficiently on a set of data, typically in O(n log n) steps. All five algorithms assume comparison of the whole key to make the decision to sort. There are simpler algorithms that can sort a list using partial information about the keys. There are two algorithms we discussed in this section called Bucket Sort and radix Sort.

Bucket Sort

The idea of the bucket sort is to place items into various buckets based on a key or partial information about a key. For example, if we have a list that contains only numbers from 0.. 99, then we can take 10 buckets and place all elements that are between 0..9 into first bucket, 10..19 into second bucket etc. This is a kind of sorting that only requires O(n) steps. A more general sorting algorithm is the radix sort that works as follows.

Suppose we are able to compare parts of the data to make a decision. Say we have a bunch of numbers we need to sort. Assume we have the following numbers.

12, 67, 45, 42, 18, 60

Assume we have 10 buckets we can work with. First we place each item in the bucket based on the least significant digit (that is 1 place). So we have the numbers in buckets as follows.

42

60                    12                                45                    67        18

0         1          2          3          4          5          6          7          8          9

Next we sort the numbers again by second digit (that is 10 place) and place them in buckets. In the process we need to make sure that we are not changing the order of the elements.

18                                45                    67

12                                42                    60

0         1          2          3          4          5          6          7          8          9

Now note that if we just collect the numbers from left to right, and bottom to top in each bucket, we have a sorted list of numbers. This is called the Radix Sort and complexity of the Radix Sort is O(nb) where b is the number of digits in the largest number.

Note radix sort can be applied to data that can be compared partially like integers of characters. However, Radix sort cannot be applied to data that needs to be compared as a whole (eg: nodes)