AceSorting  0.2
Sorting algorithms for Arduino (Bubble Sort, Insertion Sort, Shell Sort, Comb Sort, Quick Sort)
Functions
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.

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 >
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 >
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...
 

Detailed Description

Quick sort algorithms.

Definition in file quickSort.h.

Function Documentation

◆ quickSortMedian()

template<typename T >
void ace_sorting::quickSortMedian ( 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
Ttype of data to sort

Definition at line 81 of file quickSort.h.

◆ quickSortMedianSwapped()

template<typename T >
void ace_sorting::quickSortMedianSwapped ( 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.

Template Parameters
Ttype of data to sort

Definition at line 128 of file quickSort.h.

◆ quickSortMiddle()

template<typename T >
void ace_sorting::quickSortMiddle ( 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
Ttype of data to sort

Definition at line 48 of file quickSort.h.