quickSort.h File Reference

#include "swap.h"

Include dependency graph for quickSort.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_QUICK_SORT   1
	If set to 1, use the direct inlined implementation of the 2-argument quickSortXxx(). More...

Functions
template<typename T >
void	ace_sorting::quickSortMiddle (T data[], uint16_t n)
	Quick sort using Hoare's original partition where the pivot is the middle of the array. More...
template<typename T , typename F >
void	ace_sorting::quickSortMiddle (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument quickSortMiddle() with the addition of a lessThan lambda expression or function. More...
template<typename T >
void	ace_sorting::quickSortMedian (T data[], uint16_t n)
	Quick sort using Sedgewick's recommendation of using the median of low, middle and high. More...
template<typename T , typename F >
void	ace_sorting::quickSortMedian (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument quickSortMedian() with the addition of a lessThan lambda expression or function. More...
template<typename T >
void	ace_sorting::quickSortMedianSwapped (T data[], uint16_t n)
	Same as quickSortMedian(), but swap the low and high so that low, mid, and high elements become sorted. More...
template<typename T , typename F >
void	ace_sorting::quickSortMedianSwapped (T data[], uint16_t n, F &&lessThan)
	Same as the 2-argument quickSortMedianSwapped() with the addition of a lessThan lambda expression or function. More...

Detailed Description

Quick sort algorithms. See https://en.wikipedia.org/wiki/Quicksort

Definition in file quickSort.h.

Macro Definition Documentation

ACE_SORTING_DIRECT_QUICK_SORT

#define ACE_SORTING_DIRECT_QUICK_SORT   1

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

Otherwise, use the 3-argument quickSortXxx() to implement 2-argument quickSortXxx().

Unlike other sorting algorithms, the compiler cannot seem to optimize away the extra level of indirection, probably due to the recursive calls. We save 40 bytes of flash (out of 200-300 bytes) by setting this to 1 so that the 2-argument variant is manually inlined.

Definition at line 48 of file quickSort.h.

Function Documentation

quickSortMedian() [1/2]

template<typename T >

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

Quick sort using Sedgewick's recommendation of using the median of low, middle and high.

If the original array is already close to sorted or reverse sorted, this algorithm runs in O(N log(N)). Average complexity: O(N log(N))

See https://en.wikipedia.org/wiki/Quicksort

Template Parameters

T	type of data to sort

Definition at line 143 of file quickSort.h.

quickSortMedian() [2/2]

template<typename T , typename F >

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

Same as the 2-argument quickSortMedian() 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 197 of file quickSort.h.

quickSortMedianSwapped() [1/2]

template<typename T >

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

Same as quickSortMedian(), but swap the low and high so that low, mid, and high elements become sorted.

This means that the low and high are already partitioned, so we can omit those 2 points from the partitioning while-loop. This code consumes a lot more flash memory due to the additional swap() calls, but runs slightly faster.

Template Parameters

T	type of data to sort

Definition at line 247 of file quickSort.h.

quickSortMedianSwapped() [2/2]

template<typename T , typename F >

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

Same as the 2-argument quickSortMedianSwapped() 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 301 of file quickSort.h.

quickSortMiddle() [1/2]

template<typename T >

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

Quick sort using Hoare's original partition where the pivot is the middle of the array.

If the original array is already close to sorted, this algorithm runs in O(N log(N)). Average complexity: O(N log(N))

See https://en.wikipedia.org/wiki/Quicksort

Template Parameters

T	type of data to sort

Definition at line 64 of file quickSort.h.

quickSortMiddle() [2/2]

template<typename T , typename F >

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

Same as the 2-argument quickSortMiddle() 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 107 of file quickSort.h.