How is qsort(1) implemented?

Amit Alan Green aug at cybvax0.UUCP
Tue Aug 27 19:09:28 AEST 1985


I want to be able to use qsort(1) on different machine.  Below is my first
attempt to simulating this; however:

1.  Does anyone have a pubic-domain version of this which actually uses
    quick-sort rather than shell-mertzner sort? (Does anyone know the
    relative merits of these two sorts?)
2.  Can the internal loop for switching the items be improved (bcopy(1) maybe?)

Please respond by mail.

------

/*
 *	This is an attempted simulation of qsort(1) from BSD 4.2 using
 *	a shell-merztner sort.
 */
typedef int (*pfuncint) () ;

qsort (av, ac, size, func)
char *av;
int ac;
int size;
pfuncint func;
{
    int binary;
    int bytes;
    int cnt;
    int cnt2;
    register int i;
    register char *swap1;
    register char *swap2;
    char swapi;

    bytes = ac * size;
    for (binary = ac >> 1 ;  binary > 0 ;  binary >>= 1)
    {
	cnt = binary * size;
	for (cnt2 = cnt ;  cnt2 < bytes ;  cnt2 += size)
	{
	    for (swap1 = av + (cnt2 - cnt) ;
	         swap1 >= av && (*func) (swap1, swap2 = swap1 + cnt) > 0;
	         swap1 -= cnt)
	    {
		for (i = 0 ;  i < size ;  i ++)
		{
		    swapi = swap1[i];
		    swap1[i] = swap2[i];
		    swap2[i] = swapi;
		}
	    }
	}
    }
}



More information about the Comp.unix.wizards mailing list