smoothsort.c File Reference

Smoothsort implementation. More...

#include <stdlib.h>
#include <sofia-sip/su_config.h>
#include "config.h"
#include <sofia-sip/heap.h>
#include <assert.h>
#include <stdio.h>
#include <sys/types.h>

Include dependency graph for smoothsort.c:

Data Structures
struct	stretch
	Description of current stretch. More...
struct	array
	Description of array. More...
Functions
void	su_smoothsort (void *base, size_t r, size_t N, int(*less)(void *m, size_t a, size_t b), void(*swap)(void *m, size_t a, size_t b))
	Sort array using smoothsort.

---

Detailed Description

Smoothsort implementation.

Smoothsort is a in-place sorting algorithm with performance of O(NlogN) in worst case and O(n) in best case.

See also:

"Smoothsort, an alternative for sorting in-situ", E.D. Dijkstra, EWD796a, <http://www.enterag.ch/hartwig/order/smoothsort.pdf&gt;.

Author:

Pekka Pessi <Pekka.Pessi@nokia-email.address.hidden>

---

Function Documentation

void su_smoothsort	(	void *	base,
		size_t	r,
		size_t	N,
		int(*)(void *m, size_t a, size_t b)	less,
		void(*)(void *m, size_t a, size_t b)	swap
	)

Sort array using smoothsort.

Sort N elements from array base starting with index r with smoothsort.

Parameters:

	base	pointer to array
	r	lowest index to sort
	N	number of elements to sort
	less	comparison function returning nonzero if m[a] < m[b]
	swap	swapper function exchanging elements m[a] and m[b]