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: