shellSort.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	ACE_SORTING_DIRECT_SHELL_SORT   0
	If set to 1, use the direct inlined implementation of the 2-argument shellSortXxx(). More...

Functions
template<typename T >
void	ace_sorting::shellSortClassic (T data[], uint16_t n)
	Shell sort with gap size reduced by factor of 2 each iteration. More...
template<typename T , typename F >
void	ace_sorting::shellSortClassic (T data[], uint16_t n, F &&lessThan)
	Shell sort with gap size reduced by factor of 2 each iteration. More...
template<typename T >
void	ace_sorting::shellSortKnuth (T data[], uint16_t n)
	Shell sort using gap size from Knuth. More...
template<typename T , typename F >
void	ace_sorting::shellSortKnuth (T data[], uint16_t n, F &&lessThan)
	Shell sort using gap size from Knuth. More...
template<typename T >
void	ace_sorting::shellSortTokuda (T data[], uint16_t n)
	Shell sort using gap sizes empirically determined by Tokuda. More...
template<typename T , typename F >
void	ace_sorting::shellSortTokuda (T data[], const uint16_t n, F &&lessThan)
	Shell sort using gap sizes empirically determined by Tokuda. More...

Detailed Description

Shell sort with different gap algorithms. See https://en.wikipedia.org/wiki/Shellsort

Definition in file shellSort.h.

Macro Definition Documentation

ACE_SORTING_DIRECT_SHELL_SORT

#define ACE_SORTING_DIRECT_SHELL_SORT   0

If set to 1, use the direct inlined implementation of the 2-argument shellSortXxx().

Otherwise, use the 3-argument shellSortXxx() to implement 2-argument shellSortXxx(). For shellSortXxx(), the compiler will optimize both versions to be identical.

Definition at line 42 of file shellSort.h.

Function Documentation

shellSortClassic() [1/2]

template<typename T >

void ace_sorting::shellSortClassic	(	T	data[],
		uint16_t	n
	)

Shell sort with gap size reduced by factor of 2 each iteration.

Average complexity: Between O(n^1.3) to O(n^1.5) See https://en.wikipedia.org/wiki/Shellsort

Template Parameters

T	type of data to sort

Definition at line 82 of file shellSort.h.

shellSortClassic() [2/2]

template<typename T , typename F >

void ace_sorting::shellSortClassic	(	T	data[],
		uint16_t	n,
		F &&	lessThan
	)

Shell sort with gap size reduced by factor of 2 each iteration.

Average complexity: Between O(n^1.3) to O(n^1.5) See https://en.wikipedia.org/wiki/Shellsort

Template Parameters

T	type of data to sort
F	type of lambda expression or function that returns true if a < b

Definition at line 99 of file shellSort.h.

shellSortKnuth() [1/2]

template<typename T >

void ace_sorting::shellSortKnuth	(	T	data[],
		uint16_t	n
	)

Shell sort using gap size from Knuth.

Average complexity: Between O(n^1.3) to O(n^1.5)

Template Parameters

T	type of data to sort

Definition at line 169 of file shellSort.h.

shellSortKnuth() [2/2]

template<typename T , typename F >

void ace_sorting::shellSortKnuth	(	T	data[],
		uint16_t	n,
		F &&	lessThan
	)

Shell sort using gap size from Knuth.

Average complexity: Between O(n^1.3) to O(n^1.5)

Template Parameters

T	type of data to sort
F	type of lambda expression or function that returns true if a < b

Definition at line 185 of file shellSort.h.

shellSortTokuda() [1/2]

template<typename T , typename F >

void ace_sorting::shellSortTokuda	(	T	data[],
		const uint16_t	n,
		F &&	lessThan
	)

Shell sort using gap sizes empirically determined by Tokuda.

See https://en.wikipedia.org/wiki/Shellsort and https://oeis.org/A108870. Average complexity: Between O(n^1.3) to O(n^1.5)

Template Parameters

T	type of data to sort
F	type of lambda expression or function that returns true if a < b

Definition at line 285 of file shellSort.h.

shellSortTokuda() [2/2]

template<typename T >

void ace_sorting::shellSortTokuda	(	T	data[],
		uint16_t	n
	)

Shell sort using gap sizes empirically determined by Tokuda.

See https://en.wikipedia.org/wiki/Shellsort and https://oeis.org/A108870. Average complexity: Between O(n^1.3) to O(n^1.5)

Template Parameters

T	type of data to sort

Definition at line 268 of file shellSort.h.