---
name: "wnrsrt"
section: "3"
platform: "linux"
package: "libwn-dev"
version: "6.0-17"
release: "Debian 4.0 (Etch)"
platforms: ["linux"]
url: "https://new.carta.tech/wnrsrt"
---

# wnrsrt(3)

radix sorting package

## NAME

wn\_radix\_sort\_sll - radix sorting package

## SYNOPSIS

```
wn_radix_sort_sll(&list,pkeyindex_func,pkeylen_func)
wn_sll list;
char (*pkeyindex_func)(/*key,index*/); /* ptr key; int index; */
int (*pkeylen_func)(/*key*/); /* ptr key; */

```

## DESCRIPTION

**wn\_radix\_sort\_sll** sorts a singly linked list into ascending order, using a "radix sort" algorithm.  (\**pkeyindex\_func*)() returns char *index* of the key pointed to by the contents field of a wn\_sll.  (\**pkeylen\_func*)() returns the length of the key pointed to by the contents field of a wn\_sll.

This sort is much faster than the sorts in "wnsort" for large lists; however, it is slower for \|list\| \< 500 items.  It is also less flexible:  sorts based on some keys are impossible (double and float, for example).  For keys where a radix sort is applicable, such as int, pointer, or character string, I recommend this sort over "wnsort" if speed is at all important.

## EXAMPLES

The following subroutine

example1()    /\* list radix sort \*/ { extern int wn\_strlen(); char string\_index(); char \*string; wn\_sll *list*,el;

*list* = NULL;

wn\_sllins(&*list*,(ptr)"foo"); wn\_sllins(&*list*,(ptr)"bar"); wn\_sllins(&*list*,(ptr)"tim"); wn\_sllins(&*list*,(ptr)"mouse"); wn\_sllins(&*list*,(ptr)"ant"); wn\_sllins(&*list*,(ptr)"turkey");

**wn\_radix\_sort\_sll**(&*list*,(string\_index),(wn\_strlen));

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

printf("%s0,string); } }

local char string\_index(string,index) char string\[\]; int index; { return(string\[index\]); }

prints the sorted strings

ant bar foo mouse tim turkey

## RESOURCES

This routine runs with

WORST and AVERAGE CASE:

time = 1000 + sum\_over\_items(length of the key of the item) \
 stack memory = 1000\
 dynamic memory = 0

For fixed length keys, this becomes

WORST and AVERAGE CASE:

time = 1000 + number\_of\_items\*key\_length \
 stack memory = 1000\
 dynamic memory = 0

This sort is much faster than the sorts in "wnsort" for large lists; however, it is slower for \|list\| \< 500 items.  This is because of the large fixed time overhead.

For large lists, this algorithm essentially examines each char of each key exactly once.

## SEE ALSO

wnsort, [qsort(3)](/qsort/3.md), wnsll

## AUTHOR

Will Naylor