Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!uunet!elroy.jpl.nasa.gov!usc!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!dkuug!diku!bombadil
From: bombadil@diku.dk (Kristian Nielsen)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Keywords: sorting, Combsort
Message-ID: <1991May9.125814.18725@odin.diku.dk>
Date: 9 May 91 12:58:14 GMT
References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> <1991May6.155148.1201@zorch.SF-Bay.ORG> <231b3678.673637576@fergvax>
Sender: bombadil@freja.diku.dk
Organization: Department of Computer Science, U of Copenhagen
Lines: 47

231b3678@fergvax.unl.edu (Phil Dietz) writes:


>I was VERY amazed at the comb-sorts results.  I ran the test on my system, and
>you know what, comb-sort beat qsort by a heinous time!  I sorted
>a list of ints (100000 of them).  I used the comb-sort routine directly
>from the article, and I used qsort routine that comes with Lattice.
> 
>   sorting the same list of 100000 elements:   qsort  165.3 secs
>                                                comb   53.2 secs
> 
>This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW!

>Yes 3 times faster!   Here is the source code to compile on your system:
>Keep in mind that I just threw this together....(wnat some spaghetti ? :-)
> 
>Compile   lc -Lm -O  comb.c

>   if (atoi(argv[1])==1) 
>      {
>      printf("Comb Sorting:\n");
>      combsort(list,size);
>      }
>   else 
>      {
>      printf("Q-Sorting\n");
>      qsort(list,size,sizeof(int),sortfunct);
>      }
>  
>int sortfunct(int *a, int *b)
>    {
>    if (*a>*b) return  1;
>    if (*a<*b) return -1;
>    return 0;
>    }

  Though this is not a claim of qsort being better that compsort (I really
wouldn't know), it should be remarked that the above isn't really a fair way
to compare the two algorithms. The reason is that the qsort function used is
much more general than the compsort, being able to sort elements of any size
and ordering. This introduces rather large overheads in the inner loops, since
qsort has to make a function call for each compare, and perhaps also for each
element swap (memcpy?). Combsort does all of this inline, optimised for a
fixed size. How about rewriting compsort to be as general as qsort
(caller-specified size and ordering-function), and posting the results?

	- Kristian.