Prev: DPA-128 block ciphering questions
Next: jobs
From: Martin Knoblauch Revuelta on 10 Apr 2008 13:49
I am very interested in the sorting algorithm Combsort. It is
basically a modified Bubblesort that exploits the concept of
exchanging far elements. Quicksort and Shellsort are based on the same
idea.

There is a very good descrition of Combsort in the Wikipedia (http://
en.wikipedia.org/wiki/Comb_sort). In short: As Bubblesort, Combsort
iterates several times along the data, comparing pairs of elements and
swapping them if they are not in order with respect to each other. The
difference is that Bubblesort always compares/swaps contiguous
elements, while Combsort compares/swaps elements separated by a gap.
The initial gap is the size of the array, and it is divided by a
shrink factor every time the end is reached. Finally, several passes
(hopefully just one) with gap 1 end the job.

Stephen Lacey and Richard Box ("A Fast, Easy Sort", Byte, April 1991)
found experimentally an "ideal" shrink factor of 1.3. With a patch
that they called Combsort11, they claimed to "kill all miniturtles".
Though, with today's computers, it is easy to find sequences that
require several passes with a final gap of 1. The number of passes
required is low, but it seems to be proportional to the size of the
array. This makes Combsort suspicious of O(n^2) time (worst case).

NOTE: In May 1997, D. J. Bernstein wrote in comp.theory:
> Background: Knuth, in exercise 5.2.1-40, described
> a variant of Shellsort where you don't back up when
> the step size exceeds 1. This was reinvented many
> years later and presented as ``Combsort,'' with
> massive hype, in the April 1991 BYTE.

The Wikipedia also mentions a theoretical shrink factor 1/(1-exp(-
phi)) = 1.247330950103979 that guarantees that only one pass of gap 1
is required. That is, it guarantees O(n log n) worst case time.

The question is: Can anybody prove it?

The sources of this magical number have been evaporated. Does anybody
know where this came from?

I tried myself the shrink factor 1.247... and I didn't find any
"killer" sequence requiring more than one pass with gap 1.

Other sources (evaporated too) mention larger values for the shrink
factor. I tried to find, by binary search, the exact boundary. My
results suggest that a shrink factor strictly lesser than 9/7 is safe.

Note that I can only prove that 9/7 (and all other greater values I
tried) are _not_ safe. Indeed, 1.279604943109628 is mentioned in the
talk page of the Wikipedia... making me suspect that somebody found a
sequence that would kill <9/7. By the way, does anybody know such
sequence?

Here is the code written in 'non-cryptic' C:
--------------------------------------------------------
void combsort_9_7 (unsigned int A[], unsigned int len)
{
unsigned int i, j, tmp, gap;

gap = len;
// No "sorted" flag! The number of
while (gap>1) // iterations only depends on the size
{
if (gap<10) // Below 10, descend one
gap = gap - 1; // by one until zero
else
gap = (gap*7)/9 + 1; // Integer division!!
// +1: ensure shrink factor
i = 0; // strictly < 9/7
j = gap;

while (j<len) // Make a pass with current gap
{
if (A[i]>A[j]) // If not sorted ...
{
tmp = A[i];
A[i] = A[j]; // ... swap!
A[j] = tmp;
}

i = i + 1; // Advance
j = j + 1;
}
}
}
--------------------------------------------------------

And here is the 'true' C version (probably generates the same
assembler output):
--------------------------------------------------------
void combsort_9_7 (unsigned A[], unsigned len)
{
unsigned i, j, tmp, gap;

gap = len;

while (gap>1)
{
gap = gap<10 ? gap-1 : gap*7/9+1;

for (i=0, j=gap; j<len; i++, j++)
if (A[i]>A[j])
{
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
}
--------------------------------------------------------

The reason why I am so interested in Combsort is the combination of:
a) good worst-case behaviour (only if a proof is found...)
b) simplicity
c) predictability (memory addresses are always accessed in the same
fashion)

This eases the calculation of the worst case execution time, making
Combsort a good candidate for Real Time applications.

By the way, here are some timings in seconds, for sequences of 88145
elements with no repeated values:

Combsort 0.0187 (see code above)
Heapsort 0.0143 (optimized chain-swaps)
Quicksort 0.0134 (pivot chosen at random,
explicit stack and careful tail recursion
avoid function calls and stack overflow,
switch to selection sort when size<=8)

With 429993 elements:

Combsort 0.0926 seconds
Heapsort 0.0794 "
Quicksort 0.0676 "

Hardware used: PC with Intel Core 2 T7200 @ 2GHz, 2GB of RAM

Thanks in advance,
Martin
 | 
Pages: 1
Prev: DPA-128 block ciphering questions
Next: jobs