Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!rpi!dali.cs.montana.edu!caen!math.lsa.umich.edu!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!bagate!cbmvax!cbmehq!cbmger!peterk
From: peterk@cbmger.UUCP (Peter Kittel GERMANY)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Keywords: sorting, Combsort
Message-ID: <1207@cbmger.UUCP>
Date: 7 May 91 08:00:39 GMT
References: <1193@cbmger.UUCP> <1991May3.165222.31097@uokmax.ecn.uoknor.edu>
Reply-To: peterk@cbmger.UUCP (Peter Kittel GERMANY)
Organization: Commodore Bueromaschinen GmbH, West Germany
Lines: 64

In article <1991May3.165222.31097@uokmax.ecn.uoknor.edu> rrmorris@uokmax.ecn.uoknor.edu (Rodney Raym Morrison) writes:
>In article <1193@cbmger.UUCP> peterk@cbmger.UUCP (Peter Kittel GERMANY) writes:
>>Anybody read the April Byte and the article about the new Combsort
>>algorithm? Recommended to everyone.
>>But, for the best, if you look closely into one of the explanation
>>boxes, you find all this research (they obviously did an awful lot)
>>was done on an A2000.
>>    ^^^^^^^^^^^^^^^^
>>I also thought at first, be careful it's the April issue, but I
>>immediately tested it and it seems to work, flawlessly and blindingly
>>fast. It looks as if it will replace my old loved heapsort that I used
>>the last years (I hate recursive algorithms like quicksort), because
>>Combsort beats Heapsort by a factor of 33 % on my machine (e.g. 12 s
>>against 16 s).
>
>Could you post your combsort code or email it to me?

I got some more similar requests, so here we go.
Naturally, we speak AmigaBASIC (-: for the not BASIC literates there
is also a C version in the Byte article :-) :

rem Combsort, by Richard Box and Stephen Lacey, Byte 4/91, p.315
rem Sort Array a(1) to a(size), start index 0 no problem (change FOR)
gap=size
flag=-1:rem this is a boolean flag
while flag or gap<>1
  gap=int(gap/1.3):if gap<1 then gap=1
  if gap=9 or gap=10 then gap=11
  flag=0
  for i=1 to size-gap
    j=i+gap
    if a(i)>a(j) then
      ah=a(i):a(i)=a(j):a(j)=ah
      flag=-1
      end if
    next
  wend

Well, originally they use a "DO ...  UNTIL flag=0 and gap" in
TrueBasic, which is not available in AmigaBASIC. You may well do
it that way in assembler. (I hope my WHILE does indeed exactly
the same.)

The only place where you had to change something to work on an
array starting with index 0 is the FOR loop.

For the assembler gurus:
The crucial part is that divisor 1.3. If you are going fixed point
in assembler, you need not use it to 12 digits precision, values between
1.28 and 1.31 are nearly as good. So you may choose some value that
shows some easy-to-divide bit pattern. (They show a diagram made up
of 20,000 test arrays and different gap values, showing the sort time
depending on gap. The curve shows a definite minimum at 1.3, leading
into chaos for bigger values, and steadily rising for lower values.)

The special treatment of gap=9 or 10 is already a refinement of
2nd stage, not needed vitally, but reportedly optimizing the performance
and really easy to implement.

Have fun and tell me about your results!

-- 
Best regards, Dr. Peter Kittel  // E-Mail to  \\  Only my personal opinions... 
Commodore Frankfurt, Germany  \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk