wnsort(3)

NAME

wn_sort_sll, wn_sort_ptrarray - sorting package

SYNOPSIS

#include <wn/wnsort.h>
wn_sort_sll(&list,pcompare_func)
wn_sll list;
int (*pcompare_func)(/*p1,p2*/); /* ptr p1,p2; */
wn_sort_ptrarray(array,size,pcompare_func)
ptr array[];
int size;
int (*pcompare_func)(/*p1,p2*/); /* ptr p1,p2; */

DESCRIPTION

wn_sort_sll sorts a singly linked list into ascending or

der, using a "merge sort" algorithm. (*pcompare_func)() compares

contents fields of 2 wn_sll's and returns an int < == or > to 0,

according to whether object p1 is < == or > to p2.

wn_sort_ptrarray sorts (in place) array into ascending or

der, using a "quick sort" algorithm. size is the number of en

tries in array. (*pcompare_func)() compares 2 array entries and

returns an int < == or > to 0, according to whether object p1 is

< == or > to p2. Note that wn_sort_ptrarray understands only

pointers to structs, unlike qsort(3), which can manipulate an

array of structs directly.

I recommend use of wn_sort_sll rather than

wn_sort_ptrarray because lists are generally simpler and more

flexible than arrays. See "wnrsrt" for a radix list sort; this

is often much faster than wn_sort_sll or wn_sort_ptrarray.

If you must use an array-based sort, I recommend use of

wn_sort_ptrarray rather than "qsort(3)" for the following rea

sons:

1) wn_sort_ptrarray has no degenerate cases, unlike

qsort(3). If qsort(3) is passed sorted or almost sorted data or

data with many of the keys equal, it degenerates into a time=n^2

algorithm.

2) wn_sort_ptrarray is faster for non-degenerate data for

several reasons.

3) wn_sort_ptrarray is easier to understand.

EXAMPLES

Both of the following subroutines
example1() /* list sort */
{
wn_sll list,el;
char *string;

list = NULL;

wn_sllins(&list,"foo");
wn_sllins(&list,"bar");
wn_sllins(&list,"tim");
wn_sllins(&list,"mouse");
wn_sllins(&list,"ant");
wn_sllins(&list,"turkey");

wn_sort_sll(&list,(strcmp));

for(el=list;el!=NULL;el=el->next)
{
string = el->contents;

printf("%s0,string);
}
}

example2() /* array sort */
{
char *array[] =

{"foo","bar","tim","mouse","ant","turkey"};
int i;

wn_sort_ptrarray((ptr *)array,6,(strcmp));

for(i=0;i<6;i++)
{
printf("%s0,array[i]);
}
}
print the sorted strings
ant
bar
foo
mouse
tim
turkey

RESOURCES

Both of these routines run with

WORST and AVERAGE CASE:

time = n*log(n)*<time for compare>
stack memory = log(n)
dynamic memory = 0

where n is the number of items to sort.

See "wnrsrt" for a radix list sort; this is often much

faster than wn_sort_sll or wn_sort_ptrarray.

SEE ALSO

wnsrtl, wnrsrt, qsort(3), wnsll, wnrndl, wnrndp

AUTHOR

Will Naylor

WNLIB August 23, 1998

WNSORT(3)