Expert: Joseph Moore - 6/5/2009

Question
Hi Joseph,

How are you? I was wondering if I could ask you a sorting question. I have a table where rows are numbers that are in ascending order like this:
1,3,6,8,9
2,4,5,6
5,7,8,9
2,3,6,7,8
I'd like to sort my table lexicographically like this:
1,3,6,8,9
2,3,6,7,8
2,4,5,6
5,7,8,9
What is the best way to achieve that? My implementations are awfully slow. I first sort the table according to column 5, then column 4 .... until I work my way down to column 1. I've also thought about converting column rows into text strings and using string comparison to do the sort but that solution seems not very elegant. I'm thankful for any ideas you might have. Sincerely, Eric

Answer
Hi, Eric.  Your solution is almost right, it's just backwards.  Essentially, what you need to do is exactly what your second idea would do.

The string comparison algorithm starts at the beginning of the string and works forwards through the string, comparing each index until a difference is found.  In this way, no needless comparisons are made.

I would also recommend, rather than sorting the entire set one column at a time, sort one entry at a time.  There are plenty of very fast sorting algorithms out there, quicksort probably being the most popular fast algorithm, though it can be a bit dodgy to implement if you aren't familiar with it.  Bubble sort is easy to implement, but slower.

My recommended solution would be to implement a comparison function and a sort function.  The comparison function would take two rows and return which is less than the other, in much the same way that string comparisons work.  The sort function would take a set of rows and a function pointer to the comparison function, then perform the necessary operations to put them in order.  In this way, you can easily replace either piece of the application if you decide to approach it in a different manner.  (For example, you could start with a simple bubble sort implementation, just so you can get it running quickly, then work on moving to a quicksort.)