algorithms Namespace Reference

Classes
class	heap

Functions
template<class type >
basis::astring	dump_list (type v[], int size)
	dumps the contents of the list out, assuming that the type can be turned into an int. More...
template<class type >
void	shell_sort (type v[], int n, bool reverse=false)
	shell sort algorithm. More...
template<class type >
basis::array< type >	merge (basis::array< type > &first, basis::array< type > &second, bool reverse)
template<class type >
basis::array< type >	merge_sort (const basis::array< type > &v, bool reverse=false)
template<class type >
void	heap_sort (type v[], int n, bool reverse=false)
template<class type >
void	swap_values (type array[], int a, int b)
	swaps the values in the array stored at positions a and b. More...
template<class type >
int	partition (type a[], int start, int end, bool reverse)
template<class type >
void	inner_quick_sort (type v[], int start, int end, bool reverse)
	the recursive version of quick sort that does the work for our convenience method. More...
template<class type >
void	quick_sort (type v[], int n, bool reverse=false)
template<class type >
void	randomize_list (type v[], int n)
	handy method for randomizing the order of a list. not strictly a sorting function... More...

Function Documentation

dump_list()

template<class type >

basis::astring algorithms::dump_list	(	type	v[],
		int	size
	)

dumps the contents of the list out, assuming that the type can be turned into an int.

Definition at line 38 of file sorts.h.

heap_sort()

template<class type >

void algorithms::heap_sort	(	type	v[],
		int	n,
		bool	reverse = false
	)

heap sort

operates in O(n log(n)). sorts the original array.

Definition at line 283 of file sorts.h.

References algorithms::heap< type >::sift_down(), and algorithms::heap< type >::swap_values().

inner_quick_sort()

template<class type >

void algorithms::inner_quick_sort	(	type	v[],
		int	start,
		int	end,
		bool	reverse
	)

the recursive version of quick sort that does the work for our convenience method.

Definition at line 336 of file sorts.h.

References partition().

Referenced by quick_sort().

merge()

template<class type >

basis::array<type> algorithms::merge	(	basis::array< type > &	first,
		basis::array< type > &	second,
		bool	reverse
	)

sorted array merge

merges two sorted arrays into a single sorted array.

Definition at line 99 of file sorts.h.

References basis::array< contents >::length(), and basis::array< contents >::zap().

Referenced by merge_sort().

merge_sort()

template<class type >

basis::array<type> algorithms::merge_sort	(	const basis::array< type > &	v,
		bool	reverse = false
	)

merge sort

operates in O(n log(n)) time. returns a new array with sorted data.

Definition at line 131 of file sorts.h.

References basis::array< contents >::length(), merge(), and basis::array< contents >::subarray().

partition()

template<class type >

int algorithms::partition	(	type	a[],
		int	start,
		int	end,
		bool	reverse
	)

Definition at line 312 of file sorts.h.

References swap_values().

Referenced by inner_quick_sort().

quick_sort()

template<class type >

void algorithms::quick_sort	(	type	v[],
		int	n,
		bool	reverse = false
	)

quick sort

operates in O(n log(n)) time on average, worst case O(n^2). sorts the original array.

Definition at line 353 of file sorts.h.

References inner_quick_sort().

randomize_list()

template<class type >

void algorithms::randomize_list	(	type	v[],
		int	n
	)

handy method for randomizing the order of a list. not strictly a sorting function...

Definition at line 362 of file sorts.h.

References randomizer, and swap_values().

shell_sort()

template<class type >

void algorithms::shell_sort	(	type	v[],
		int	n,
		bool	reverse = false
	)

shell sort algorithm.

Sorts a C array of the "type" with "n" elements. Operates on the original array. Performs within O(n^2) time (depending on the gap size used). Algorithm is based on Kernighan and Ritchie's "The C Programming Language".

Definition at line 55 of file sorts.h.

Referenced by filesystem::directory::rescan(), and configuration::system_values::text_form().

swap_values()

template<class type >

void algorithms::swap_values	(	type	array[],
		int	a,
		int	b
	)

swaps the values in the array stored at positions a and b.

Definition at line 303 of file sorts.h.

Referenced by partition(), and randomize_list().