We’re storing selected sessions in a Hashtable structure, using the SessionID as the key. We could have stored them into a SortedArray structure and keep them ordered by start date/time, but SortedArray is another one of those features left on the chopping block by .NET CF. So, we have to find a way to display the sessions nicely sorted.
There are at least 683 available sort routines. Probably more since I started writing this post. All have some qualities and all have some drawbacks. My design analysis (see previous post for details) and usability lab tests discovered that we’re going to spend much more time in looking at sessions, back and forth from the search page, than actually adding or removing them from our selected list. So it would make sense to keep them sorted right from the beginning, instead or rearranging them everytime we want to display the list.
There is a method for the task list component called Add. Surprisingly enough, this method inserts a new Session in the list and then calls a sort function to fit it in the right position. The sort function used is bubble sort.
I can hear already the warcries. “What about QuickSort?!” Yeah yeah, true, but let’s think for a moment about our particular case. QuickSort is very efficient in sorting large amounts of very sparse data, but BubbleSort has its own advantages too.
The following analysis is supported by these four guys that had the courtesy to make me avoid doing math. This is a good thing both for you and for me.
Let’s see… BubbleSort requires ((N^2 – N) / 2) comparisons to completely finish the algorithm. Scary for high (> 50) values of N. On the other hand, QuickSort requires ((N / 2) * N Log(2)) comparisons. The absence of the ^2 is a good plus for QuickSort 🙂
But… for small values of N, as in our case with sessions, BubbleSort is actually faster and given that we execute the sort everytime we add a new session, it only has to “bubble” one item at a time.
So, BubbleSort it is. And if any of the other 685 sort methods will prove to be more efficient, it won’t be a problem to change it in the control. Later.