Sorting Algorithms: Integer Sorts

For my last entry, I'm going to try to cover integer sorting. This isn't something we have really touched on in class, but something that I decided to look into after the performance of count sort in the trials that Danny ran, and from Danny saying that Radix sort is his favourite sorting algorithm.

From what I've read, there are two approaches to sorting. There are comparison sorts(like mergesort) and then there are integer sorts, like the aforementioned count sort and radix sort.

We went over count sort in class, and it's pretty simple. It takes a list of integers, and forms a new list with a placeholder value for each item in the input list(ie, the length of the new list is the number of items in the input list). It then reads out of the indices into a new list and returns it. This has the effect of sorting the list of integers. The flaws in this approach are pretty obvious. While the algorithm will handle the list [3,2,0,1] with ease, it can't handle something like [11,3,46], or even [5,0]. This is because the index numbers won't correspond to the integer values. This makes the algorithm seem a little bit useless to me(maybe it's just the implementation we used?). But it's useful to illustrate the difference between integer sorts and comparison sorts, as an exemplar of the approach of the latter. Count sort(perhaps to its detriment, and utility) doesn't even look at the input values, besides how many of them there are. Compare(ha!) this to something like mergesort, whose approach to sorting depends on looking at, and comparing, theses very values.

The other type of integer sort I'm going to try to cover is Radix sort, which is the professor's favourite. Now, we didn't really cover radix sort at all in class, so I had to look into it. This obviously won't be an in-depth treatment, but I'll see what I can do. There seems to be a couple of different implementations of radix sort, the main distinction being on sorting by least or most significant digit. I'll just cover the LDS sort here. Now, as radix sort is an integer sorting algorithm, it doesn't sort the values directly. It depends instead on keys. It seems to me that if you are sorting a list of integers, then it's pretty safe to have the keys directly correspond to the integers you're dealing with, but I suppose it'd be a different story if you had to deal with strings or such. Now, once you have these keys, you sort them by the LDS of each one. You organise your keys by their LDSes, and pass over them repeatedly, moving them accordingly. Eventually you wind up with a list keys that are properly sorted.

Now obviously(and probably evidently) I haven't delved into this very deeply, but it seems pretty nifty to me. Apparently radix is a preferred algorithm for comparing text strings, but I wasn't quite able to figure out why, as it seems to me that the obvious way to use it(sorting a list of keys based on the length of the strings) doesn't lend itself to radix sort more than any other sorting algorithm. But it's late, and maybe I'm just being stupid!

This was my last entry, thanks for reading!