combSort.h File Reference

#include "swap.h"

Include dependency graph for combSort.h:

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

Go to the source code of this file.

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

Functions
template<typename T >
void	ace_sorting::combSort13 (T data[], uint16_t n)
	Comb sort using a gap factor of 1.3 (successive gap is multiplied by 10 / 13). More...
template<typename T , typename F >
void	ace_sorting::combSort13 (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument combSort13() with the addition of a lessThan lambda expression or function. More...
template<typename T >
void	ace_sorting::combSort13m (T data[], uint16_t n)
	Same as combSort13() with the modification that if the gap is 9 or 10, it is set to 11, so that the gap sequence becomes (11, 8, 6, 4, 3, 2, 1). More...
template<typename T , typename F >
void	ace_sorting::combSort13m (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument combSort13m() with the addition of a lessThan lambda expression or function. More...
template<typename T >
void	ace_sorting::combSort133 (T data[], uint16_t n)
	Comb sort using a gap factor of 4/3=1.33 (successive gap is multiplied by 3 / 4). More...
template<typename T , typename F >
void	ace_sorting::combSort133 (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument combSort133() with the addition of a lessThan lambda expression or function. More...
template<typename T >
void	ace_sorting::combSort133m (T data[], uint16_t n)
	Same as combSort133() but modified so that a gap of 9 or 10 becomes gap=11 so that the final sequence becomes (11, 8, 6, 4, 3, 2, 1). More...
template<typename T , typename F >
void	ace_sorting::combSort133m (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument combSort133m() with the addition of a lessThan lambda expression or function. More...

Detailed Description

Comb sort.

Definition in file combSort.h.

Macro Definition Documentation

ACE_SORTING_DIRECT_COMB_SORT

#define ACE_SORTING_DIRECT_COMB_SORT   0

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

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

Definition at line 43 of file combSort.h.

Function Documentation

combSort13() [1/2]

template<typename T >

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

Comb sort using a gap factor of 1.3 (successive gap is multiplied by 10 / 13).

On 8-bit processors where the int type is 2 bytes, the multiplication of n by 10 can overflow the 16-bit integer. So the largest n that this function can support is 65536 / 10 or 6553.

Average complexity: O(n^2 / 2^p). See https://en.wikipedia.org/wiki/Comb_sort

Template Parameters

T	type of data to sort

Definition at line 82 of file combSort.h.

combSort13() [2/2]

template<typename T , typename F >

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

Same as the 2-argument combSort13() with the addition of a lessThan lambda expression or function.

Template Parameters

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

Definition at line 98 of file combSort.h.

combSort133() [1/2]

template<typename T >

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

Comb sort using a gap factor of 4/3=1.33 (successive gap is multiplied by 3 / 4).

The multiplication by 3 can overflow the 2-byte int type on 8-bit processors, so the largest n supported by this function is 65535 / 3 or 21845.

This gap ratio seemed appealing because the division by 4 will be optimized by the compiler into a right shift of 2 bits, so this algorithm does not perform any integer division. Experimentation on 8-bit processors without hardware dvision shows that this algorithm is slightly faster than combSort13() on average.

On 32-bit or 64-bit processors with hardware division, on larger input data, experimentation shows that this algorithm is actually slightly slower on average than combSort13(). And it seems to have a slightly higher variance, with some input data causing large spikes in runtime compared to the average.

Average complexity: O(n^2 / 2^p). See https://en.wikipedia.org/wiki/Comb_sort

Template Parameters

T	type of data to sort

Definition at line 247 of file combSort.h.

combSort133() [2/2]

template<typename T , typename F >

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

Same as the 2-argument combSort133() with the addition of a lessThan lambda expression or function.

Template Parameters

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

Definition at line 263 of file combSort.h.

combSort133m() [1/2]

template<typename T >

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

Same as combSort133() but modified so that a gap of 9 or 10 becomes gap=11 so that the final sequence becomes (11, 8, 6, 4, 3, 2, 1).

Experimentation shows that this is often slightly slower than than combSort133(), probably due to the extra if/then/else statements in the loop.

Average complexity: O(n^2 / 2^p). See https://en.wikipedia.org/wiki/Comb_sort

Template Parameters

T	type of data to sort

Definition at line 323 of file combSort.h.

combSort133m() [2/2]

template<typename T , typename F >

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

Same as the 2-argument combSort133m() with the addition of a lessThan lambda expression or function.

Template Parameters

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

Definition at line 339 of file combSort.h.

combSort13m() [1/2]

template<typename T >

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

Same as combSort13() with the modification that if the gap is 9 or 10, it is set to 11, so that the gap sequence becomes (11, 8, 6, 4, 3, 2, 1).

For reasons that I don't understand, this makes the algorithm faster and more resistence to outliers.

Average complexity: O(n^2 / 2^p). See https://en.wikipedia.org/wiki/Comb_sort and https://rosettacode.org/wiki/Sorting_algorithms/Comb_sort.

Template Parameters

T	type of data to sort

Definition at line 159 of file combSort.h.

combSort13m() [2/2]

template<typename T , typename F >

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

Same as the 2-argument combSort13m() with the addition of a lessThan lambda expression or function.

Template Parameters

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

Definition at line 175 of file combSort.h.