A comparison of Quick Sort vs. Comb Sort using C++ and Ruby
Plus some implementations of Combsort in other languages
by Wayne Conrad
Every programmer knows that quicksort is the best in-memory sort in the world. Look inside the sort function of almost any library and you'll find quicksort. Another thing that every programmer knows is that bubblesort, the "hello world" of sorts, is one of the worst in the world. But what most programmers don't know is that a simple modification to bubble sort turns it into combsort, a remarkably simple sort that's nearly as fast as quicksort. It's so simple that you can commit it to memory and call on it any time you need a sort and don't have one available.
In this article, I will show code and benchmarks for quicksort and combsort using both C++ and Ruby. You will see how quicksort compares to combsort, and how Ruby compares to C++. And there's a surprise in the comparison of an in-place quicksort in Ruby to one that returns a new copy of the array.
CPU seconds to sort a scrambled list of 10,000 consecutive integers
C++ Ruby Quicksort (in-place) 0.0038 1.73 Quicksort (copy) n/a1 1.46 Combsort 0.0042 2.48 Bubblesort 1.36 851.15 built-in sort 0.0024 0.01
Read on (or click on the numbers) to see the code for each benchmark.
Here's the algorithm from quicksort.cpp. This is based upon the algorithm presented by Mark Brettin 2:
static int partition(int a[], int first, int last) { int pivot = a[first]; int lastS1 = first; int firstUnknown = first + 1; while (firstUnknown <= last) { if (a[firstUnknown] < pivot) { lastS1++; std::swap(a[firstUnknown], a[lastS1]); } firstUnknown++; } std::swap(a[first], a[lastS1]); return lastS1; } static void quicksort(int a[], int first, int last) { if (first < last) { int pivotIndex = partition(a, first, last); quicksort(a, first, pivotIndex - 1); quicksort(a, pivotIndex + 1, last); } } static void quicksort(int a[], int aSize) { quicksort(a, 0, aSize - 1); }
C++ Quicksort sorts 10,000 items in 0.0038 seconds.
A naive quicksort like this one is very slow in the presence of an already sorted (or almost sorted) list. There are several common optimizations for quicksort that will take care of that problem. One is to look at the first, middle, and last item in the list and use the one that's between the other two. Another, even easier fix is to just pick the pivot point at random 3. This is a surprisingly good fix: Although any one randomly chosen pivot point might be very bad, the odds that too many bad pivot points will be chosen is quite small. In any case, because this deficiency of quicksort is so easy to fix, and because it won't change the performance of quicksort much, we won't worry about already sorted lists in this comparison. That lets me get on with the job of showing off combsort and not spend my time optimizing quicksort for worst cases.
static void bubblesort(int a[], int aSize) { for (;;) { bool swapped = false; for (int i = 0; i < aSize - 1; i++) { int j = i + 1; if (a[i] > a[j]) { std::swap(a[i], a[j]); swapped = true; } } if (!swapped) break; } }
C++ bubblesort sorts 10,000 items in 1.36 seconds.
Here's the algorithm from combsort.cpp. The differences from C++ bubblesort are highlighted.
static int newGap(int gap) { gap = (gap * 10) / 13; if (gap == 9 || gap == 10) gap = 11; if (gap < 1) gap = 1; return gap; } static void combsort(int a[], int aSize) { int gap = aSize; for (;;) { gap = newGap(gap); bool swapped = false; for (int i = 0; i < aSize - gap; i++) { int j = i + gap; if (a[i] > a[j]) { std::swap(a[i], a[j]); swapped = true; } } if (gap == 1 && !swapped) break; } }
C++ combsort sorts 10,000 items in 0.0042 seconds, only 1.1 times longer than C++ quicksort. It's amazing that such a simple change to bubblesort makes it nearly as good as quicksort. What's more, combsort doesn't need any special code to keep from degenerating in the presence of already sorted lists.
Combsort starts out comparing items that are far apart. Then it makes the gap smaller and does it again. In the algorithm's last passes the gap is 1, making it act identical to bubblesort. That makes it easy to see that this algorithm is correct, since we know that bubblesort is correct and this algorithm always turns into bubblesort.
The newGap function contains some magic spells.
Stepehn Lacey and Richard Box showed that the gap should be divided by
1.3 on each pass. They also found that gaps of 9 and 10 are bad and are
best replaced with a gap of 115.
(Further research by Jim Veale suggests that a carefully made table of gaps
can improve performance further6).
static void builtinsort(int a[], int aSize) { sort (a, a + aSize); }
This executes in 0.0024 seconds, faster than any other sort we benchmark here. I only looked inside the STL code long enough to become horribly confused, but it's obvious from the speedy execution that S++'s implementation of STL is using QuickSort. It's probably also using the optimization of using insertion sort for short arrays.
def partition(a, first, last) pivot = a[first] lastS1 = first firstUnknown = first + 1 while firstUnknown <= last do if a[firstUnknown] < pivot lastS1 += 1 a.swap(firstUnknown, lastS1) end firstUnknown += 1 end a.swap(first, lastS1) lastS1 end def quicksort(a, first = 0, last = a.size - 1) if first < last pivotIndex = partition(a, first, last) quicksort(a, first, pivotIndex - 1) quicksort(a, pivotIndex + 1, last) end end
The Ruby in-place quicksort runs in 1.73 seconds, a whopping 453 times what C++ in-place quicksort takes. It's even slower than C++ bubblesort. Ruby is much slower than C++ at hand-coded sorts (although Ruby's built-in sort doesn't do too bad).
Out of curiosity, I tried implementing the version of quicksort that returns a copy of the array rather than modifying it in place. This algorithm is quite beautiful, but seems like it would be much slower than an in-place sort. I wanted to see how much slower. Here's the algorithm (source unknown 7) from QuickSort.rb:
def quicksort(a) return a if a.size <= 1 pivot = a[0] quicksort(a.select {|value| value < pivot}) + a.select {|value| value == pivot} + quicksort(a.select {|value| value > pivot}) end
This runs in 1.46 seconds. And there's the surprise: It's faster, not slower than in-place QuickSort's 1.73 seconds. My common sense says that this algorithm, which is making and concatenating lots of little arrays, should be slower than the in-place algorithm. And yet it's not. Perhaps the select method is so fast that it makes up for all of the array copies and concatenations.
def bubblesort(a) loop do swapped = false (a.size - 1).times do |i| j = i + 1 if a[i] > a[j] a.swap(i, j) swapped = true end end break if !swapped end end
This runs in 851.15 seconds. Yikes!
def combsort(a) b = a gap = b.size loop do gap = gap * 10 / 13 gap = 11 if gap == 9 || gap == 10 gap = 1 if gap < 1 swapped = false (b.size - gap).times do |i| j = i + gap if b[i] > b[j] b.swap(i, j) swapped = true end end break if gap == 1 && !swapped end b end
This runs in 2.48 seconds, more than twice as slow as Ruby Quicksort but still in the running as a very fast sort algorithm.
This executes in 0.01 seconds, 4 times what C++'s built-in sort takes. Internally,def builtInSort(a) a.sort! end
Array.sort! (the method being called here) is
using quicksort. It's slower than C++'s quicksort because everything
in Ruby is an object. Each integer in the array is a separate object,
and the array contains references to those objects. Considering all
that, it's pretty impressive that Ruby's built-in sort is that fast.
The benchmarks were run on this computer:
Model Dell® Inspiron 4000 CPU Intel® P3/5508 RAM 128MB9 Operating system Linux 2.2.19
The C++ benchmarks were compiled with g++ 2.95.2 using -O3 (full frontal optimization). A typical compile command is:
g++ -o quicksort -O3 quicksort.cpp
The Ruby benchmarks were run with Ruby 1.6.4.
Here's combsort in some other languages. These aren't benchmarks, just the sort and a small "main" (or whatever passes for a "main") to show that it works.
Be sure to look at Nick Estes' Introduction to a disturbing hobby. Combsort in Postscript? Weird!1I didn't do a benchark of a C++ quicksort that returns a copy of the array (rather than modifying it in place) because it seems too hard to bother with.
2 Quick Sort Algorithm / Analysis by Mark Brettin.
3 Analysis of Quicksort (6), Michael L. Littman, September 15th, 1998.
4Bubblesort is actually not too bad if the list is nearly sorted or if the list is very small. For any other case, it's pretty bad.
5 A Fast Easy Sort, Stephen Lacey and Richard Box.
6 An Improved Comb Sort with Pre-Defined Gap Table by Jim Veale.
7 I don't remember where I got this algorithm from, but I doubt it's mine. I vaguely remember that quicksort in Haskell is as beautiful, so I might have stolen this from a Haskell example.
8The laptop's CPU has Intel® SpeedStep™ technology, which just means that it can run faster when the laptop is plugged into the wall. However, I've configured the laptop to always run at the same speed — battery speed — even when it's plugged in. When the laptop runs at full speed, the exhaust from its cooling fan cooks my leg. A lucky side-effect of disabling SpeedStep is that the benchmarks always run at the same speed whether I'm mobile or plugged in.
9All benchmarks ran entirely out of RAM. No swap file was harmed in the running of these benchmarks.
10 Nick Estes, the hacker behind the Perl version, insisted that I include an obfuscated version as well. Do Perl programs always come in readable/unreadable pairs?
Richard Box and Stephen Lacey, "Byte magazine," April 1991.
Sorting Algorithms by Leif Svalgaard, CobolReport.com. Comparisons of sorting algorithms, including combsort.