A89: Re: Some sorting extras. :)


[Prev][Next][Index][Thread]

A89: Re: Some sorting extras. :)




Ok, standard divide by two then. I guess there is no reson to use any other on
an implementation like this :)
I don't even know why I asked really :)
But there are others. any will do really, as long as the last pass is gap = 1.
divide with 2 is the first that Shell did, then there is divide with 2.2 and
there is also a special series that goes 1,4,13,40,...
where gap(i) = 3*gap(i-1)+1.
They affect how many passes and swaps that needs to be done, and tries to
minimize unnessesary compares.
Knuths gap-stepping 1,4,13,40,... could maybe be worth trying on the 89. muls
and divs are slow though, but maybe it is faster anyway :)  at least on larger
amounts of data.

Sorting is fun :)

//Olle

Zeljko Juric wrote:
> 
> Hi!
> 
> You asked me about gap in ShellSort? OK, here is an implementation,
> look and see:
> 
> void qsort(void *list,int num_items,int size,long(*cmp_func)(void*,void*))
> {
>   unsigned gap,byte_gap,i,j;
>   char *p,*a,*b,temp;
>   for (gap=num_items>>1;gap>0;gap>>=1)
>     {
>       byte_gap=gap*size;
>       for(i=byte_gap;i<num_items*size;i+=size)
>         for(p=(char*)list+i-byte_gap;p>=(char*)list;p-=byte_gap)
>           {
>             a=p; b=p+byte_gap;
>             if(cmp_func(a,b)<=0) break;
>             for(j=size;j;j--) temp=*a,*a++=*b,*b++=temp;
>           }
>     }
> }
> 
> Zeljko Juric



References: