Sorting Algorithms: The Comb Sort
Welcome to this, the third post in the series on sorting algorithms. Next up, we’re going to cover the Comb Sort.
Like the Cocktail Sort, the Comb Sort isn’t particularly well known. Most people manage to make their way through tertiary studies without ever hearing of it. This post is designed to change that!
The Comb Sort is another comparison and exchange sort which builds on the idea of the Bubble Sort and adds a potential optimisation or two.
Make sure you read the articles on the Bubble Sort and the Cocktail Sort before you read this article. Doing so will make it much easier to understand.
Right, enough with the introductions, let’s break it down!
Common Terms
- Data set - the array or list of items that is to be sorted.
- n - the number of elements in the data set.
- Turtle - a name given to small numbers that appear towards the end of a data set. When used in a Bubble Sort, small numbers at the end of the set take a very long time to get to the front of the list, and hence are called turtles because of the lack of speed.
- Hare - a name given to large numbers that appear towards the start of a data set. When used in a Bubble Sort, large numbers move to the end of the set very quickly, and hence are called hares due to their high speed.
- Killing the turtles - a phrase that implies quickly moving turtles to the front of the data set.
- Gap - the size of the gap between areas of the data set that are being sorted during a given iteration of the sort.
- Shrink Factor - a factor which is applied to the gap prior to each iteration to reduce its size.
A Bit of Background Information
The Comb Sort, along with the Cocktail Sort, was developed as an improvement to the Bubble Sort using the idea of killing the turtles. Turtles drastically reduce the efficiency of the Bubble Sort and hence are an obvious place to attempt optimisation.
The Bubble Sort algorithm always compares values that are adjacent to each other in the data set. The Comb Sort improves on this by adding a gap which allows non-adjacent numbers to be compared. After each iteration, the gap is reduced by a shrink factor until it reaches the value of 1. Hence, at the very end, the Comb Sort behaves exactly like the Bubble Sort.
One interesting thing to note about this algorithm is that it’s almost as fast as a Quick Sort!
The Algorithm
Each iteration of the algorithm consists of three stages:
- Calculation of the gap value.
- Iterating over the data set comparing each item with the item that is “gap” elements further down the list and swapping them if required.
- Checking to see if the gap value has reached one and no swaps have occurred. If so, then the set has been sorted.
1. Calculating the “gap”
The gap, which is essentially an offset used when comparing elements, is something that changes for each iteration. The value needs to change in a uniform manner in such a way as to provide optimum comparisons during the sorting phases.
Stephen Lacey and Richard Box, who popularised the algorithm, suggested that in each iteration the gap should be reduced by a factor of approximately 1.3 (see the wikipedia article for more information). Hence, calculation of the gap is as simple as starting with the size of the data set and dividing by a shrink factor of 1.3 each iteration.
2. Iterating and Swapping
This phase is the same as the Bubble Sort. The only difference in the Comb Sort is that the items which are compared are i and i + gap as opposed to i and i + 1.
For each iteration, we start at the beginning of the data set and loop until i + gap is greater-than or equal to the size of the data . For each sub-iteration in this loop, we compare i and i + gap and swap the values if required.
At this point the gap is recalculated and we go again.
3. Terminating the Loop
When the gap value reaches one, we know that we’re now behaving the same as the Bubble Sort algorithm (since we’re comparing i and i + 1), so we know that if we don’t perform any swaps during the iteration then the set must be sorted.
The Example
As per usual we will use the same initial data set that we used for the Bubble Sort and Cocktail Sort to aid in highlighting the differences.
The initial set looks like this:
33 98 74 13 55 20 77 45 64 83
We start by setting our gap value to 10, which is the size of the set. We then shrink the gap by the shrink factor, 1.3, which results in the value of 7 (when rounded down).
The first iteration starts at the beginning of the set, comparing the 1st item with the item that is “gap” elements further up the set (the 8th item). These two items are shown in red:
33 98 74 13 55 20 77 45 64 83
33 is less than 45, so no swap is required. We then move to the 2nd item, and compare that item with the 9th item:
33 98 74 13 55 20 77 45 64 83
We perform a swap at this point because 98 is bigger than 64. The swap is shown in blue:
33 64 74 13 55 20 77 45 98 83
We then move on to compare the 3rd and 10th elements:
33 64 74 13 55 20 77 45 98 83
Again, no swap is required here as the numbers are in the right order.
At this point we have completed our first iteration as we’ve reached the end of the set. Given that the gap value is not 1, we know we still have more iterations to go. So we need to recalculate our gap value by dividing it again by the shrink factor, resulting in a value of 5 (after rounding down).
We then start another iteration from the beginning of the set, using the gap value of 5 as the offset. We start with the 1st and 6th items:
33 64 74 13 55 20 77 45 98 83
Given 33 is bigger than 20, we swap:
20 64 74 13 55 33 77 45 98 83
Then we compare the 2nd and 7th items:
20 64 74 13 55 33 77 45 98 83
No swap required, move to the 3rd and 8th items:
20 64 74 13 55 33 77 45 98 83
Perform the swap since 74 is bigger than 45:
20 64 45 13 55 33 77 74 98 83
We then compare the 4th and 9th items:
20 64 45 13 55 33 77 74 98 83
No swap required, compare the 5th and 10th items:
20 64 45 13 55 33 77 74 98 83
Again, no swap required. We’ve hit the end of this next iteration, and since gap doesn’t equal 1, we recalculate (resulting in the value of 3) and go again.
This time I’ll just show a summary of the steps:
20 64 45 13 55 33 77 74 98 83
13 64 45 20 55 33 77 74 98 83
13 64 45 20 55 33 77 74 98 83
13 55 45 20 64 33 77 74 98 83
13 55 45 20 64 33 77 74 98 83
13 55 33 20 64 45 77 74 98 83
13 55 33 20 64 45 77 74 98 83
13 55 33 20 64 45 77 74 98 83
13 55 33 20 64 45 77 74 98 83
13 55 33 20 64 45 77 74 98 83
Again, we iterate the value of gap, which becomes 2, and we go again:
13 55 33 20 64 45 77 74 98 83
13 55 33 20 64 45 77 74 98 83
13 20 33 55 64 45 77 74 98 83
13 20 33 55 64 45 77 74 98 83
13 20 33 55 64 45 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
Finally, we reduce the value of gap one more time, resulting in the value of 1. We’re finally at the Bubble Sort stage, and hence the last iteration looks like this:
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 64 55 77 74 98 83
13 20 33 45 55 64 77 74 98 83
13 20 33 45 55 64 77 74 98 83
13 20 33 45 55 64 77 74 98 83
13 20 33 45 55 64 74 77 98 83
13 20 33 45 55 64 74 77 98 83
13 20 33 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
At this point we know, due to observation, that the list is sorted. Unfortunately, the algorithm is yet to know. It looks at the value of gap and sees that it is set to 1, but during the last iteration there were swaps — so the code will iterate again.
At the end of this iteration, given that there were no swaps, it will know that the list is sorted and the code will terminate.
The Implementation
Here is a sample implementation written in C#. It is heavily commented in the hope that it will aid in understanding how the algorithm works:
/// <summary> /// The implementation of the standard comb sort algorithm which sorts /// an array of integers. /// </summary> /// <param name="dataSet">Reference to the dataset that is to be soroted.</param> static void CombSort(int[] dataSet) { // start by using the length/size of the set as the gap. int gap = dataSet.Length; // loop indefinately. while (true) { // update the gap value so that it shrinks // towards 1. if (gap > 1) { gap = (int)((double)gap / SHRINK_FACTOR); } // do the comb sort with the current gap bool swapped = false; for (int i = 0; i + gap < dataSet.Length; ++i) { if (dataSet[i] > dataSet[i + gap]) { Swap(dataSet, i, i + gap); swapped = true; } } // if we're down to a gap of 1, and we haven't swapped // anything, then we're sorted. if (gap == 1 && !swapped) { break; } } }
The Complexity
This is quite surprising. Despite being based on the idea of a Bubble Sort the time complexity is just O(n log n), and space complexity for in-place sorting is O(1). Amazing for such a simple sorting algorithm!
A Note on Performance
What I’m about to say is almost a direct rip-off of Wikipedia 
But at least I’m being honest!
When you use a shrink factor of 1.3, as recommended, it turns out that there are only 3 ways for the gap sizes to reduce to 1. They are:
1. - 9, 6, 4, 3, 2, 1
2. - 10, 7, 5, 3, 2, 1
3. - 11, 8, 6, 4, 3, 2, 1
According to Wikipedia, it turns out that the 3rd option is the only one which manages to kill all turtles before the gap becomes 1. I haven’t been able to find anything that backs this up though.
Assuming that this is true, we can create a modified version of the Comb Sort which has this extra little check:
if(gap == 9 || gap == 10) { gap = 11; }
This is a little hack which makes sure that we get the third option before we reduce the gap to 1. Of course, this would only have an effect on sets of data which have more than 11 elements.
Other Implementations
I’m slowly gathering a collection of implementations of all the sorting algorithms, including the ones listed above, that I’m covering in this series and posting them up on BitBucket. The Comb Sort implementations can be found here.
Note: You’ll need Mercurial if you want to pull directly from the repository, otherwise you’ll have to copy and paste from the web.
References and Other Information
Next up, we’ll be looking at the Gnome Sort.
Disclaimer
I’m no expert, nor an authority. The post above is based on my experience and a bit of research. If you find something wrong with anything I’ve said please let me know. Comments and feedback are greatly appreciated.
Note: For those reading this article in an RSS reader, you may find the colours do not appear in the examples properly. For some reason the feed is stripping out some of the formatting. I will do my best to fix this up soon.
Nice one OJ, I must say I hadn’t really considered the Comb sort before.
I like it when algorhithms have a bit of esoterica about them (i.e factor of 1.3) because to the casual observer, you wouldn’t necessarily know why it works, but rather just taking a leap of faith! I also like these because it seems to me that someone cared deeply enough to find that magic (read: most efficient) factor, which means they spent considerable time on it - more than I’m prepared to - so I appreciate their hard work. Let’s face it - a lot of people would say “just use Bubble Sort”. But these guys went the extra mile…
Anyways, that being said - are you going to eventually get to a point in this series where you explain when you’d use, say “quick sort” over this one (since you noted it was almost as fast)?
What I’m getting at here is pragmatic use of sorting in real world code. Do you think developers should build up a sorting library (on a given project) so that they can call Sorting.Quicksort(dataset) or Sorting.Combsort(dataset) at will depending on the characteristics of the data, or would they instead just implement a “general purpose” sort (i.e. choose their favourite) and apply that in all cases in an application?
Not sure where I stand on this - can’t remember the last time I used sort beyond List<T>.Sort(). Didn’t exactly get to choose the explicit algorhithm there if you know what I mean - just trust the framework dudes know what they’re doing right?
Nice post mate,
Cheers,
Rob G
Hey OJ. Never heard of this one before so it’s good to do a bit of learning on a Sunday after football!
I have one question though, when shrinking the gap value I assume it’s more efficient to use the rounded down value for each division rather than the ‘true’ value? i.e. in your example the gap values are 10, 7, 5, 3, 2, 1, whereas if you used the non-rounded version each time you get 10, 7(.69), 5(.91), 4(.55), 3(.50), 2(.69), 2(.07), 1(.59). In this case you get two more gap values of 4 and 2 but I don’t know if this will help or hinder the algorithm.
Generally if i’m doing something like this where i’m dividing a number repeatedly i’d always use the non-rounded version (for example moving sprites around the screen works a lot better incrementing the ‘true’ position rather than the rounded one).
Good read,
Gavin
Hi Oj!
Interesting one mate. Hadn’t heard of comb sort before… Something new every day
One thing I’d love to see in these articles is some kind of ‘timeline of invention’ - i.e. you talk about Comb Sort improving on Bubble Sort - it would be great to know how long it took for this algorithm to emerge, and who put the work into designing it.
Given the different space requirements, I guess I’m most curious to find out whether this was developed after Quicksort…
Have a good Monday! (Still enjoying Sunday here!)
Nick
@Everyone: I hadn’t heard of the Comb Sort before embarking on this little series. It’s quite nifty. Unfortunately the example I use above isn’t exactly a great example in that it actually takes more iterations than the Bubble sort, though the number of exchanges/compares might be a bit less.
Either way, I learned something new. So this little series is already proving its worth for me!
The next one, Gnome Sort, is another I hadn’t heard of. So hopefully we’ll all get something out of that one too.
@Rob: I’m the same mate. Quirkiness is an interesting thing
When I get the chance I’m going to try and understand the theory behind why 1.3 (or more specifically 1 / (1 - (1 / e^phi)) approx = 1.247330950103979) is the magic number in this case, though I’m struggling to find resources.
Your question about “when to you use sort X” is a good one. It’s something that I am aiming to tackle at the end of the series. I had originally intended to include that information in each post, but I think it’s probably a better option to reflect when the series is over and explain when to use each in a single post.
Real-world is definitely a goal here. It’s all well and good to learn the algorithms and improve your knowledge, but knowing when and where to apply it is key. I think in most cases the framework of choice can be trusted to deal with sorting for you (as per your List.Sort() example). I think this is fine, but moreso because usually the amount of data you’re dealing with is quite small. As we know, everything is fast for small values of n.
If you found yourself in a different scenario where you were actually working on some software which required sorting of enormous datasets, then I think you’d start to hate the baked-in List.Sort() solution.
So as I said, I’ll aim to hit this information at the end of the series. I’ll most likely do a comparison of each algo over a series of different datasets to see how they perform relatively as well.
Cheers!
@Gav: I had pondered the same question when I was writing the code myself. At what point should I be rounding? Should I just round off each time I calculate? Or round off only when using it as an offset? I too noticed that there were cases where you’d get 2 appearing twice.
That to me was a bit of a signal that I wasn’t doing what the authors of the algorithm intended. So I decided to round each time. I was going to have a dabble with a couple of bigger datasets to see if this would have any affect. Given that the example code I’ve seen on the web does the same as what I’ve already done I’d assume that this is the preferred option.
Watch this space though. If I get the chance I’ll respond with my findings (feel free to do the same and let me know
).
Cheers!
@Nick: That’s something I hadn’t considered. I think a timeline would also be neat. I night edit my posts to date and retrofit a mini time-line. As I post each article I’ll add the new sort to the timeline. This, of course, assumes that the date of conception of the algos is known
Thanks for the suggestion mate, I reckon other people will find it interesting too!
Good luck tomorrow on your first day. Hope it goes well
Nice post, and not a bad algorithm either! However, I find myself a little wary of where the 1.3 magic number comes from. Is it just a case of “this seems to work well” or have they actually proved it’s particularly efficient for a wide selection of datasets.
@Keef: That’s a question I’m trying to answer myself mate. On the surface the whole idea makes sense to me, but I’m still unsure where the magic number comes from. I am trawling for some theory but not really turning up much. I’m kinda hoping that a math’s wonk will come on here and tell us why
If I find something I’ll be sure to post it. If you happen to stumble on something please let me know
Cheers!
on the subject of rounding, you (and the authors) state that 1.3 is the best value to use and wikipedia states that the acutal value is 1 / (1 - (1 / e^phi)), approx = 1.247330950103979. So in the case of the magic value you round up, but the gap you round down.
Seems a little odd to be rounding up the magic value, especially when you could just use 1.25.
Well, as I said, I don’t know the reasons for the number, it’s something that I’m trying to determine. I can understand where you’re coming from, but using 1.25 is obviously going to result in different numbers compared to 1.3 when you start dealing with large datasets.
I don’t think that it was as simple as “the author rounded up”. I reckon it’d be more a case of “the author tried rounding in both directions, but found that 1.3 yielded better results than 1.2″. Of course, I am speculating wildly.
Cheers
This is my favourite sorting algorithm. If you use SSE on the PC, you can use min and max instructions which automatically compare and exchange values. With each register holding 4 values, you can compare 16 values at a time. With this, you use a factor of 1.6 for the gap. I found it through trial and error. But just a little off and it really degrades performance.
The really cool thing is that if you use this with insertion sort, it’s actually faster than quicksort when you have lots of random elements. What isn’t cool is that it takes the same amount of time no matter what, so it sucks for lists that are not random.
Here’s an article I wrote quite a while back trying to write a custom routine that was faster than anything out there. Comb sort did the job.
http://my.opera.com/Vorlath/blog/show.dml/94793
@Vorlath: Thanks for the comment mate. Haven’t seen you around for a while. I see you’ve had a bit of fun in the past playing around with sorting. By the end of this little series I do plan on getting a collection of datasets together and doing a few benchmarks myself. I’m not sure if I’ll get to the point where I’ll be writing ASM versions of something the algos, it depends on the time. Plus, most people won’t see a great deal of value in an ASM implementation (most.. but not all
).
I was pleasantly surprised at the results of this particular algo. Crazy/scary to think that I didn’t really know much about it until recently. Must continue reading!
Thanks for the link! Cheers.
Would you (in this series) find it interesting to cover impractical sorting algorithms (such as the Bogosort) to further explain big O notation perhaps?
http://en.wikipedia.org/wiki/Bogosort
It has an interesting thought experiment in that a quantum bogosort would be able to sort any sequence in O(n) time, but result in the destruction of n-1 universes…
I’ll definitely be covering esoteric and ridiculous sorts like the Bogosort, but they won’t appear until the end of the series