Sorting Things Out
It's time to recap a topic that is, or should be, close to the heart of every developer. A topic that is often overlooked or glossed over, rarely fully understood and not often discussed. Yet this topic is hugely important.
That topic is Sorting.
On the surface it appears to be so simple. Just arrange some stuff in a certain order. What could be easier?
Unfortunately the implementations of various methods of sorting can be anything but easy. Determining which algorithm to choose can be difficult enough given that some lend themselves to sorting certain data types better than others do.
As a result, I've decided to start writing a series on the different well-known (and perhaps not-so-well-known) sorting algorithms. For each algorithm, my goal will be to:
- Paint a very clear picture of how it functions. I aim to do this via pictures and discussion. If I get time, I will aim to provide an animated visualiser of the algorithm (though at the moment this might be a tough ask given time constraints).
- Explain the order of complexity/Big-O notation so that it's clear just how expensive it is to use, along with details of best and worst cases.
- Give examples of data sets where the algorithm fits well, and examples of where it doesn't.
- Explain if and how the given algorithm can be used in a multhithreaded environment.
- Demonstrate errors that are found frequently in various implementations (if there are any), and show how to resolve/avoid them.
By the end of the series, I hope that you (and I) will have a really solid understanding of the Sorting world.
To start off with, I'll be covering the age-old Bubble Sort. I'm choosing this because it's very simple, and is an easy target for me to get going.
As always, comments and feedback will be greatly appreciated. I'm hoping that I'll learn more from this exercise than you guys will.
August 13th, 2008 - 23:16
Bring it on! Don’t just tease us now you hear!
August 14th, 2008 - 08:51
Patience my friend, patience!
I’m 90% of the way through the first in the series.
August 14th, 2008 - 23:11
hurry up with it then OJ. I’ve been hitting refresh every five minutes waiting for this one.
August 15th, 2008 - 07:09
@secretGeek: Smart arse
April 2nd, 2009 - 21:40
Good series, I had not heard of comb sort, an amazingly simple modification of bubble sort that actually turns something awful into something reasonably efficient. My own preference is generally merge sort because it:
1. is a stable sort
2. has good worst-case behavior
3. easiest to implement for sorting large files that won’t fit into RAM
April 2nd, 2009 - 22:45
@Matt: Thank you for the feedback! I still have so many other sorts to get through, and MergeSort is on the list. You make some good points about its benefits too. It’s just a shame that there’s no catch-all solution to the sorting problem.
I’m aiming to get the Quick Sort post done in the next two weeks. So watch this space!
Cheers.