man wnsort (Fonctions bibliothèques) - sorting package
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("%sn",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("%sn",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
AUTHOR
Will Naylor