wnsort(3) · carta

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 order, 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 order, using a "quick sort" algorithm. size is the number of entries 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 reasons:

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.

AUTHOR