From: news@massey.ac.nz (USENET News System)
Newsgroups: comp.lang.pascal
Subject: Comb Sort - an optimised bubble sort (was Re: Bubble Sort Routine)
Date: 6 Oct 92 21:27:37 GMT
Article-I.D.: massey.1992Oct6.212737.11799
Organization: School of Maths. and Info. Sci., Massey University, Palmerston North, NZ

In article <1935@hsdndev.UUCP> rind@binoc.bih.harvard.edu (David Rind) writes:
>I saw an article somewhere not long ago that described a modified
>bubble sort where the elements that were being compared varied with 
>each pass according to some simple algorithm.  For instance, on the
>first pass, the sort would compare elements 1 and 10, 2 and 11, etc.
>while on another pass it might compare 1 and 5, 2 and 7, etc.  They
>ran comparisons against other sorts, and it seemed very fast for a
>bubble algorithm.  Anyone know anything about this?  Is this a
>well-described sort?
>
>-- 
>David Rind
>rind@binoc.bih.harvard.edu

Here's an implementation of the sort mentioned above and a reference.
The primary difference is that instead of comparing and exchanging
adjacent elements, it has a GAP that is initially set to about 77%
(i.e. N/1.3) of the number of elements to be sorted.  On each pass
the gap is reduced until the sort degenerates to a pure bubblesort.
However, by this time, most of the elements a near their final
destination.  The improvement is quite dramatic - see the results
after the following programs:
---------------------------------------------------------------------
program combsort_test;

{Read 10 strings from the keyboard, sort them using a COMB SORT}
{and print the sorted array with some statistics}

{For details on the Comb Sort see}
{"A Fast Easy Sort" by S.Lacy & R.Box, BYTE April 1991, pp 315-320}

{written by Giovanni Moretti, 1991.    G.Moretti@massey.ac.nz}

 var
  data : array [1..10] of string;
  temp : string;
  n, i : integer;

 procedure COMBSORT;
  var
   i, gap, comparisons, exchanges : integer;
   done : boolean;
 begin
   gap := 10;
   comparisons := 0;
   exchanges := 0;
   repeat
     gap := trunc(gap / 1.3);
     if gap < 1 then gap := 1;
     writeln('Gap = ', gap);
     done := true;
     for i := 1 to n - gap do
       begin
         comparisons := comparisons + 1;
         if data[i] > data[i + gap] then       { Out of order}
           begin
             temp := data[i + gap];            { Swap them }
             data[i + gap] := data[i];
             data[i] := temp;
             done := false;                    { Not finished}
             exchanges := exchanges + 1;
           end;
       end;
   until done and (gap = 1);   { no swaps => all sorted }
  writeln;
  writeln('Comb sort needed ', comparisons : 4, ' comparisons and ',
           exchanges : 4, ' exchanges ');
 end;

begin
 n:= 10;
 writeln('COMB SORT');
 writeln('Enter 10 strings - one to a line : ');
 for i := 1 to 10 do  readln(data[i]);
 combsort;
 for i := 1 to 10 do writeln(data[i]);
end.

========================================================================
Here's just the sort procedure stripped of all the diagnostics - it
assumes there is a global array DATA that contains the data to be sorted.

procedure COMBSORT ( n : integer) ;
var i, gap,tmp : integer;
    done       : boolean;
 begin
   gap := n;
   repeat
     gap := trunc(gap / 1.3);
     if gap < 1 then gap := 1;
     done := true;
     for i := 1  to  n - gap  do
       if data[i] > data[i + gap] then 
         begin
           tmp := data[i + gap]; 
           data[i + gap] := data[i];
           data[i] := tmp;
           done := false;  
         end;
   until done and (gap=1); 
end;


RESULTS
=======
As a test, I took several articles off the net and chopped them up
to get a file of 1550 strings, one to a line. This was used as 
test data.  

THE DATA AFTER BEING SORTED (email addresses from article headers)
===========================
!
!
!
!)
!IT
!It
!The
!ames
!ariel
!augean
!comp
!comp
!ee5391aa
!gvokalek
!hydra
!munnari
!munnari
!ncar

As it turned out, there were about 500 unique strings the rest being
duplicates.  I know this isn't scientific or anything approaching
random data, but here are the results for what they're worth.

SORTING 1550 strings
====================
Bubble sort needed  2.1million comparisons & 550000 exchanges 
Comb sort needed    37000     comparisons  &   6300 exchanges 
Quick sort needed   12000     comparisons  &   4600 exchanges 

SUMMARY (Measured sort results - Mac IILC with Macpascal)
=======
                            Comp+Exchgs   Sort Time
                            -----------   ---------
Bubblesort                    2650000    ~ 56 mins
Combsort                        43300      55 secs
Quicksort                       16600      31 secs

Slowest : fastest   ~108:1

GAP FACTOR 1.3
==========
The value of 1.3 appears to be quite critical, even small deviations
alter the final results significantly.  The original article is well
written and includes the results of sorting many lots of random data
with varying gap factors.  It's well worth reading.

Have fun
Giovanni




-- 
-----------------------------------------------------------------------------
Giovanni Moretti                                                       ZL2BOI
Computer Science Department, Massey University, Palmerston North, New Zealand
G.Moretti@massey.ac.nz      Phone +64-6-356-9099            Fax 64-6-350-5611