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