[comp.lang.pascal] New Sorting Algorithm

pwolanin@phoenix.Princeton.EDU (Peter M Wolanin) (05/23/91)

Hi everyone,

Included below is the Pascal code for a sort algorithm you may be interested
in.  It was in the April issue of BYTE magazine.  It's a non-recursive
adaptation of the standard bubblesort, but its speed is proportional
to N*ln(N). For a list of 1000 random integers, it took .28 seconds
while quicksort took .16 seconds.  A very non-optimized bubble sort took
14 seconds (all this with a 386sx-16).  Sorry if you've all seen this
before, but I don't often read this group.

-Peter

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

PROCEDURE Combsort11 ( VAR list  :list_type;
                           lo,hi :integer);

{pre :list_type is an array of data_type.  hi, lo indicate the first
       and last elements in the list.
 post: returns the list sorted low to high}

  CONST shrink = 1.3;

  VAR gap,current,size :integer;
      temp             :data_type;
      switches         :boolean;

  BEGIN
    size:=hi-lo+1; {size of list}
    gap:=size;

    REPEAT
      switches:=false;
      gap:=TRUNC(gap/shrink);
      IF gap<1
        THEN gap:=1;
      IF (gap=9) OR (gap=10) {make sure to end w/ series from 11 for max eff.}
        THEN gap:=11;
      FOR current:=lo to size-gap DO
        BEGIN
          IF list[current] > list [current+gap]
            THEN
              BEGIN
                temp:=list[current];
                list[current]:=list[current+gap];
                list[current+gap]:=temp;
                switches:=true;
              END;
        END;
    UNTIL (gap=1) AND (NOT(switches));
  END;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

DON'T PANIC! Only a week and a half more of exams!

pwolanin@phoenix.princeton.edu - Peter Wolanin