Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!kuhub.cc.ukans.edu!maverick.ksu.ksu.edu!unlinfo.unl.edu!fergvax!231b3678
From: 231b3678@fergvax.unl.edu (Phil Dietz)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Keywords: sorting, Combsort
Message-ID: <231b3678.673637576@fergvax>
Date: 7 May 91 17:32:56 GMT
References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> <1991May6.155148.1201@zorch.SF-Bay.ORG>
Sender: news@unlinfo.unl.edu
Organization: University of Nebraska - Lincoln
Lines: 119
Nntp-Posting-Host: fergvax.unl.edu

In <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes:

>While it does (barely) beat heapsort, it takes almost twice as long
>as quicksort, so it is still not a choice you'd make except in a small
>sort, quick hack application.  As a recent net posting showing
>quicksort in ML proved, there is nothing inherently complex about
>quicksort, our notation for programming just makes it look complex
>with a lanugage as weak as C.

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


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
void main(int argc, char **argv)
   {
   void combsort(int *list,int size);
   int sortfunct(int *a, int *b);
 
   int i,*list,size;
   unsigned int clock[2],clock2[2];
   
   if (argc<3)
      {
      printf("combsort  [ 1 | 2 ] [# of elements]\n 1 = comb\n 2 = qsort\n\n");
      exit(1);
      }
   size=atoi(argv[2]);
   if (size<10) exit(1);
   list=(int *)calloc(size,sizeof(int));
   if (!list)
      {
      printf(" Ran out of memory!\n");
      exit(1);
      }
   for (i=0;i<size;i++)  list[i]=(rand() % size);    /* Get random list    */
   for (i=0;i<10;i++) printf("%d: %d\n",i,list[i]);  /* Print some of them */
   
   timer(clock);
 
   if (atoi(argv[1])==1) 
      {
      printf("Comb Sorting:\n");
      combsort(list,size);
      }
   else 
      {
      printf("Q-Sorting\n");
      qsort(list,size,sizeof(int),sortfunct);
      }
 
   timer(clock2);
   printf("\nSorted:\n");
   for (i=0;i<10;i++) printf("%d: %d\n",i,list[i]);
   printf("Time 1:  %d.%d\n",clock[0],clock[1]);
   printf("Time 2:  %d.%d\n",clock2[0],clock2[1]);
   if (clock[1]>clock2[1])  
      printf("Total time:  %d.%d secs\n",(clock2[0]-clock[0]),(clock[1]-clock2[1]));
   else
      printf("Total time:  %d.%d secs\n",(clock2[0]-clock[0]),(clock2[1]-clock[1]));
   }
 
void combsort(int *list,int size)
   {
   int switches, hold, i, j, top, gap;
 
   gap=size;
   do {
      gap=(int)((float)gap/1.3);
      switch(gap)
         {
         case 0:           gap=1; break;
         case 9: case 10:         break;
         default:                 break;
         }
      switches=0;
      top=size - gap;
      for(i=0;i<top;++i)
         {
         j=i+gap;
         if (list[i] > list[j])
            {
            hold=list[i];
            list[i]=list[j];
            list[j]=hold;
            ++switches;
            }
         }
      } while (switches || (gap>1));
   }
  
int sortfunct(int *a, int *b)
    {
    if (*a>*b) return  1;
    if (*a<*b) return -1;
    return 0;
    }


---                    
   I don't like to flame!                                    Phil Dietz 
   You know what?                              231b3678@fergvax.unl.edu       
   Newton and Leibniz suck big time!                  Univ. of Nebraska