Sorting algorithms

Comparison based sorting algorithms. More...

Macros
#define	CSNIP_QSORT_STACKSZ   64
	Size of the Qsort stack. More...
#define	CSNIP_QSORT_SLIMIT   24
	Minimum Qsort partition size. More...
#define	csnip_Qsort_median3_pivot(u, v, au_lessthan_av, swap_au_av, beg, end)
	Compute median3 pivot (for Quicksort). More...
#define	csnip_Qsort_partition(u, v, au_lessthan_av, swap_au_av, beg, end, result)
	Quicksort's partition algorithm. More...
#define	csnip_Qsort(u, v, au_lessthan_av, swap_au_av, N)
	Quicksort algorithm. More...
#define	CSNIP_HEAPSORT_K   2
	Heap arity for sorting algorithm.
#define	csnip_Heapsort(u, v, au_lessthan_av, swap_au_av, N)
	Heapsort algorithm. More...
#define	csnip_Shellsort(u, v, au_lessthan_av, swap_au_av, N)
	Shellsort algorithm. More...
#define	csnip_ShellsortGS(u, v, au_lessthan_av, swap_au_av, N, nGaps, gapSeq)
	Shellsort with gap sequence. More...
#define	csnip_IsSorted(u, v, au_lessthan_av, N, ret)
	Check if an array is sorted. More...
#define	CSNIP_SORT_DECL_FUNCS(scope, prefix, gen_args)
	Declare sorting functions. More...
#define	CSNIP_SORT_DEF_FUNCS(scope, prefix, gen_args, u, v, au_lessthan_av, swap_au_av, N)
	Define sorting functions. More...

Detailed Description

Macro Definition Documentation

csnip_Heapsort

#define csnip_Heapsort	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			N
	)

Sorting algorithm. Is O(N log N) worst case, but usually significantly slower than Quicksort.

Parameters

u,v	dummy variables
au_lessthan_av	Comparator expression
swap_au_av	Statement to swap a[u] with a[v]
N	Array size

csnip_IsSorted

#define csnip_IsSorted	(		u,
			v,
			au_lessthan_av,
			N,
			ret
	)

Parameters

u,v	Dummy variables.
au_lessthan_av	Comparator expression.
N	Array size.
ret	l-value to return the result. Will be 1 if sorted, 0 if not.

csnip_Qsort

#define csnip_Qsort	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			N
	)

The classic median-of-three quicksort algorithm. This is a very fast sorting algorithm, running in O(N log N) time in typical cases, but has pathological cases of O(N^2).

Parameters

u,v	dummy variables
au_lessthan_av	Comparator expression, evaluates to true if a[u] < a[v].
swap_au_av	Statement to swap a[u] with a[v].
N	Size of the array to sort.

csnip_Qsort_median3_pivot

#define csnip_Qsort_median3_pivot	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			beg,
			end
	)

Computes a median-of-three pivot (first, middle and last element), and moves it to the beginning of the range.

Parameters

u,v	dummy variables, representing array indices.
au_lessthan_av	Expression to check whether a[u] < a[v], where a is the backing array.
swap_au_av	Statement to swap the u-th and v-th element in the backing array.
beg	index of the first element to partition.
end	index one past the last element in the range.

csnip_Qsort_partition

#define csnip_Qsort_partition	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			beg,
			end,
			result
	)

The pivot is the first element in the range. After execution of the algorithm, the given range is partitioned, such

1. The formerly first array element a[beg] is now at a[result].
2. All array entries with index < result are <= a[result].
3. All array entries with index > result are >= a[result].

Parameters

u,v	dummy variables
au_lessthan_av	Expression evaluation a[u] < a[v].
swap_au_av	Statement to swap a[u] and a[v].
beg	First index in the range to partition.
end	Last index in the range to partition.
result	l-value where the location of the pivot is returned.

CSNIP_QSORT_SLIMIT

#define CSNIP_QSORT_SLIMIT   24

Partitioning is no longer applied below the minimum size. Instead, another simple sorting algorithnm will be used.

CSNIP_QSORT_STACKSZ

#define CSNIP_QSORT_STACKSZ   64

csnip_Shellsort

#define csnip_Shellsort	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			N
	)

This sorting algorithm has unknown complexity that lies somewhere between O(N log N) and O(N^2). It is very simple, and very useful when code size matters. In practice, its run time behaviour is similar to heapsort for small to medium sized arrays.

Parameters

u,v	dummy variables
au_lessthan_av	Comparator expression
swap_au_av	Statement to swap a[u] with a[v]
N	Array size

csnip_ShellsortGS

#define csnip_ShellsortGS	(		u,
			v,
			au_lessthan_av,
			swap_au_av,
			N,
			nGaps,
			gapSeq
	)

This variant of shellsort allows for explicitly specified gap sequences.

CSNIP_SORT_DECL_FUNCS

#define CSNIP_SORT_DECL_FUNCS	(		scope,
			prefix,
			gen_args
	)

Generator macro to create prototypes for specific instances of the sorting functions.

Parameters

scope	Scope to use for the function declaration.
prefix	Prefix for the function names to be generated.
gen_args	Generic argument list to be provided to the functions, of the form args(...) or noargs().

CSNIP_SORT_DEF_FUNCS

#define CSNIP_SORT_DEF_FUNCS	(		scope,
			prefix,
			gen_args,
			u,
			v,
			au_lessthan_av,
			swap_au_av,
			N
	)

Generator macro to create for specific sorting functions.

Parameters

scope	Scope to use for the function declaration.
prefix	Prefix for the function names to be generated.
gen_args	Generic argument list to be provided to the functions, of the form args(...) or noargs().
u,v	dummy variables
au_lessthan_av	comparator expression
swap_au_av	swapping statement
N	array size