AceSorting

Various sorting functions targeted for the Arduino environment, implemented using C++11 template functions. The library is intended to be compatible with most Arduino platforms, but some tradeoffs lean in favor of lower-end processors (e.g. AVR, lower-end STM32) as opposed to higher-end processors with larger amounts of RAM (e.g. ESP32, higher-end STM32).

Supports the following algorithms:

• Bubble Sort
  • bubbleSort() (not recommended)
• Insertion Sort
  • insertionSort() (recommended if N < ~100 or a stable sort is needed)
• Selection Sort
  • selectionSort() (not recommended)
• Shell Sort
  • shellSortClassic(): gap factor 2
  • shellSortKnuth(): gap factor 3 (recommended)
  • shellSortTokuda(): gap factor 2.25
• Comb Sort
  • combSort13(): gap factor 1.3 (13/10)
  • combSort13m(): gap factor 1.3, modified for gaps 9 and 10 (recommended for 32-bit processors)
  • combSort133(): gap factor 1.33 (4/3) (recommended for 8-bit processors)
  • combSort133m(): gap factor 1.33, modified for gaps 9 and 10
• Quick Sort
  • quickSortMiddle(): pivot on middle element (recommended)
  • quickSortMedian(): pivot on median of low, mid, high
  • quickSortMedianSwapped(): pivot on median and swap low, mid, high

tl;dr

• In most cases, use shellSortKnuth().
  • It costs only 142 bytes on an AVR and 80-112 bytes on 32-bit processors.
  • It is faster than any O(N^2) algorithm while consuming only 34-82 extra bytes of flash over insertionSort().
• If N >= ~1000, and you have sufficient static memory for recursive functions, and shellSortKnuth() is not fast enough, use:
  • quickSortMiddle() on 8-bit AVR processors, and
  • quickSortMedianSwapped() on 32-bit processors.
• Use combSort133() or shellSortClassic() to get the smallest sorting function faster than O(N^2).
• Use insertionSort() if you need a stable sort.
• Don't use the C library qsort().
  • It is 2-3X slower than the quickSortXxx() functions in this library, and consumes 4-5X more in flash bytes.
• Never use Bubble Sort.
  • Insertion Sort is 5-6X faster with only a handful (0-32) bytes of extra flash.

Version: 1.0.0 (2021-12-04)

Changelog: CHANGELOG.md

Table of Contents

• Hello Sorting
• Installation
  • Source Code
  • Dependencies
• Documentation
  • Examples
• Usage
  • Include Header and Namespace
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Shell Sort
  • Comb Sort
  • Quick Sort
  • C Library Qsort
• Advanced Usage
  • Function Pointer
  • Lambda Expression
  • Compiler Optimizations
• Resource Consumption
  • Flash And Static Memory
  • CPU Cycles
• System Requirements
  • Hardware
  • Tool Chain
  • Operating System
• Bugs and Limitations
• Alternative Libraries
• License
• Feedback and Support
• Authors

<a name="HelloSorting"></a>

Hello Sorting

This is a simplified version of the examples/HelloSorting demo:

#include <Arduino.h>
#include <AceSorting.h>

using ace_sorting::shellSortKnuth;

const uint16_t ARRAY_SIZE = 20;
int array[ARRAY_SIZE];

void printArray(int* array, uint16_t arraySize) {
  for (uint16_t i = 0; i < arraySize; i++) {
    Serial.print(array[i]);
    Serial.print(' ');
  }
  Serial.println();
}

void fillArray(int* array, uint16_t arraySize) {
  for (uint16_t i = 0; i < arraySize; i++) {
    array[i] = random(256);
  }
}

void setup() {
  delay(1000);
  Serial.begin(115200);
  while (!Serial); // Leonardo/Micro

  // Attempt to get a random seed using the floating analog pin.
  randomSeed(analogRead(A0));

  fillArray();
  Serial.println("Unsorted:");
  printArray(array, arraySize);

  // The compiler automatically generates the correct version of
  // shellSortKnuth() based on the type of `array`.
  shellSortKnuth(array, arraySize);
  Serial.println("Sorted:");
  printArray(array, arraySize);
}

void loop() {}

<a name="Installation"></a>

Installation

The latest stable release is available in the Arduino IDE Library Manager. Search for "AceSorting". Click install.

The development version can be installed by cloning the GitHub repository, checking out the develop branch, then manually copying over to or creating a symlink from the ./libraries directory used by the Arduino IDE. (The result is a directory or link named ./libraries/AceSorting.)

The master branch contains the stable releases.

<a name="SourceCode"></a>

Source Code

The source files are organized as follows:

• src/AceSorting.h - main header file
• src/ace_sorting/ - implementation files
• tests/ - unit tests which require AUnit
• examples/ - example sketches
• docs/ - contains the doxygen docs and additional manual docs

<a name="Dependencies"></a>

Dependencies

This library itself does not depend on any other library.

The unit tests depend on:

• AUnit (https://github.com/bxparks/AUnit)

Some of the examples may depend on:

• AceCommon (https://github.com/bxparks/AceCommon)

<a name="Documentation"></a>

Documentation

• this README.md file
• Doxygen docs on Github pages.

<a name="Examples"></a>

Examples

• examples/HelloSorting
  • A simple demo of one of the sorting functions.
• examples/CompoundSortingDemo
  • A more complex example of sorting by a compound key, first by score, then breaking any ties by name.
• Benchmarks
  • examples/MemoryBenchmark
    • Determine flash and static RAM consumption of various algorithms.
  • examples/AutoBenchmark
    • Determine CPU runtime of various algorithms.
  • examples/WorstCaseBenchmark
    • Determine CPU runtime of worst case input data (e.g. sorted, reverse sorted).

<a name="Usage"></a>

Usage

<a name="HeaderAndNamespace"></a>

Include Header and Namespace

Only a single header file AceSorting.h is required to use this library. To prevent name clashes with other libraries that the calling code may use, all classes are defined in the ace_sorting namespace. To use the code without prepending the ace_sorting:: prefix, use the using directive to select the specific algorithm. For example, to use the shellSortKnut() function, use something like this:

#include <Arduino.h>
#include <AceSorting.h>
using ace_sorting::shellSortKnuth;

<a name="BubbleSort"></a>

Bubble Sort

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

namespace ace_sorting {

template <typename T>
void bubbleSort(T data[], uint16_t n);

}

• Flash consumption: 44 bytes on AVR
• Additional ram consumption: none
• Runtime complexity: O(N^2)
• Stable sort: Yes
• Performance Notes:
  • If data[] is already sorted, this is O(N).
  • Worst performance O(N^2) when data is reverse sorted.
• Not recommended

<a name="InsertionSort"></a>

Insertion Sort

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

namespace ace_sorting {

template <typename T>
void insertionSort(T data[], uint16_t n);

}

• Flash consumption, 60 bytes on AVR
• Additional ram consumption: none
• Runtime complexity: O(N^2) but 5-6X faster than bubbleSort()
• Stable sort: Yes
• Performance Notes:
  • If data[] is already sorted, this algorithm is O(N).
  • Worst performance O(N^2) when data is reverse sorted.
• Recommendation: Use for N smaller than about 100 and only if you need a stable sort

<a name="SelectionSort"></a>

Selection Sort

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

namespace ace_sorting {

template <typename T>
void selectionSort(T data[], uint16_t n);

}

• Flash consumption, 100 bytes on AVR
• Additional ram consumption: none
• Runtime complexity: O(N^2) but 2X slower than insertionSort()
• Stable sort: No
• Performance Notes:
  • Little change in performance when data is already sorted or reverse sorted.
• Not recommended:
  • Larger and slower than insertionSort() but is not a stable sort.
  • The only thing it has going for it is that it has the least number of writes versus reads. Might be worth looking into if writing the data is much more expensive than reading the data.

<a name="ShellSort"></a>

Shell Sort

See https://en.wikipedia.org/wiki/Shellsort. Three versions are provided in this library:

namespace ace_sorting {

template <typename T>
void shellSortClassic(T data[], uint16_t n);

template <typename T>
void shellSortKnuth(T data[], uint16_t n);

template <typename T>
void shellSortTokuda(T data[], uint16_t n);

}

• Flash consumption: 100-180 bytes of flash on AVR
• Additional ram consumption: none
• Runtime complexity: O(N^k) where k=1.3 to 1.5
• Stable sort: No
• Performance Notes:
  • As fast as Quick Sort for N <= ~300.
  • Little change in performance when data is already sorted or reverse sorted.
• Recomendation: Use shellSortKnuth(), which seems consistently faster than shellSortClassic(), just as fast as shellSortTokuda() but is simpler and takes less flash memory than shellSortTokuda().

<a name="CombSort"></a>

Comb Sort