While working on some code I needed a basic C++ sorting algorithm for a uint8_t array.
So I implemented five different ones to see the perfomance difference.
//
// FILE: sort.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: compare sorting methods
// DATE: 2014-11-20
// URL:
//
// Released to the public domain
//
uint8_t array[250];
uint32_t start;
uint32_t stop;
void setup()
{
Serial.begin(115200);
Serial.println("Start Sort\n");
randomSeed(1);
for (uint8_t i=0; i< 250; i++) array[i] = random(256);
start = micros();
bubbleSort(array, 250);
stop = micros();
Serial.print("bubbleSort:\t");
Serial.println(stop-start);
// for (uint8_t i=0; i< 250; i++)
// {
// Serial.print(array[i]);
// Serial.print(" ");
// if (i%10==0) Serial.println();
// }
Serial.println();
randomSeed(1);
for (uint8_t i=0; i< 250; i++) array[i] = random(256);
start = micros();
shellSort(array, 250);
stop = micros();
Serial.print("shellSort:\t");
Serial.println(stop-start);
// for (uint8_t i=0; i< 250; i++)
// {
// Serial.print(array[i]);
// Serial.print(" ");
// if (i%10==0) Serial.println();
// }
Serial.println();
randomSeed(1);
for (uint8_t i=0; i< 250; i++) array[i] = random(256);
start = micros();
insertSort(array, 250);
stop = micros();
Serial.print("insertSort:\t");
Serial.println(stop-start);
// for (uint8_t i=0; i< 250; i++)
// {
// Serial.print(array[i]);
// Serial.print(" ");
// if (i%10==0) Serial.println();
// }
Serial.println();
randomSeed(1);
for (uint8_t i=0; i< 250; i++) array[i] = random(256);
start = micros();
combSort11(array, 250);
stop = micros();
Serial.print("combSort11:\t");
Serial.println(stop-start);
// for (uint8_t i=0; i< 250; i++)
// {
// Serial.print(array[i]);
// Serial.print(" ");
// if (i%10==0) Serial.println();
// }
Serial.println();
randomSeed(1);
for (uint8_t i=0; i< 250; i++) array[i] = random(256);
start = micros();
quickSort(array, 250);
stop = micros();
Serial.print("quickSort:\t");
Serial.println(stop-start);
// for (uint8_t i=0; i< 250; i++)
// {
// Serial.print(array[i]);
// Serial.print(" ");
// if (i%10==0) Serial.println();
// }
Serial.println();
}
void loop()
{
}
void bubbleSort(uint8_t * ar, uint8_t n)
{
// bubble sort with flag
for (uint8_t i=0; i< n-1; i++)
{
bool flag = true;
for (uint8_t j=1; j< n-i; j++)
{
if (ar[j-1] > ar[j])
{
uint8_t t = ar[j-1];
ar[j-1] = ar[j];
ar[j] = t;
flag = false;
}
}
if (flag) break;
}
}
void shellSort( uint8_t *ar, uint8_t n)
{
uint8_t i, temp, flag = 1;
uint8_t d = n;
while( flag || (d > 1)) // boolean flag (true when not equal to 0)
{
flag = 0; // reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (n - d); i++)
{
if (ar[i + d] < ar[i])
{
temp = ar[i + d]; // swap positions i+d and i
ar[i + d] = ar[i];
ar[i] = temp;
flag = 1; // tells swap has occurred
}
}
}
}
void combSort11(uint8_t *ar, uint8_t n)
{
uint8_t i, j, gap, swapped = 1;
uint8_t temp;
gap = n;
while (gap > 1 || swapped == 1)
{
gap = gap * 10 / 13;
if (gap == 9 || gap == 10) gap = 11;
if (gap < 1) gap = 1;
swapped = 0;
for (i = 0, j = gap; j < n; i++, j++)
{
if (ar[i] > ar[j])
{
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
swapped = 1;
}
}
}
}
void quickSort(uint8_t *ar, uint8_t n)
{
if (n < 2)
return;
uint8_t p = ar[n / 2];
uint8_t *l = ar;
uint8_t *r = ar + n - 1;
while (l <= r) {
if (*l < p) {
l++;
}
else if (*r > p) {
r--;
}
else {
int t = *l;
*l = *r;
*r = t;
l++;
r--;
}
}
quickSort(ar, r - ar + 1);
quickSort(l, ar + n - l);
}
void insertSort(uint8_t * ar, uint8_t n)
{
uint8_t t, z, temp;
for (t = 1; t < n; t++)
{
z = t;
while( (z > 0) && (ar[z] < ar[z - 1] ))
{
temp = ar[z];
ar[z] = ar[z - 1];
ar[z - 1] = temp;
z--;
}
}
}
Quicksort is a clear winner, but combSort11 is a good second place as it doesn't use recursion it probably uses less RAM. I did not measure that yet as my goal was primary performance.
Difference between quickSort and combSort11 grows in absolute sense but relative it is still only 1.6x slower. The others are way behind 30-60 times slower
Interesting experiment! I've read the whole thread and I'm trying to replicate your experiment (for 16 bit numbers), but having trouble getting the code to run.
I tried looking at your code but there's no comments anywhere and the way testSort interprets its arguments goes way over my head. Could anyone help me out? I'm getting the error:
error: cannot convert 'int (*)[4]' to 'int*' for argument '1' to 'void quickSort(int*, int)'
Which I guess means that the 'int' that quickSort works on cannot point to the array that I fed it, because it's not compatible? Don't really understand this.
Minimum code to reproduce this is here:
int myArray[] = {4,8,2,11};
int sortedArray[4];
void setup() {
// put your setup code here, to run once:
}
void loop() {
// put your main code here, to run repeatedly:
sortedArray = quickSort(&myArray, 4);
}
void quickSort(int *ar, int n)
//the local 'ar' variable, through the dereference operator * now
//points to the array that you fed it with the dereference operator &
{
if (n < 2) //array too small
return;
int p = ar[n / 2];
int *l = ar;
int *r = ar + n - 1;
while (l <= r) {
if (*l < p) {
l++;
}
else if (*r > p) {
r--;
}
else {
int t = *l;
*l = *r;
*r = t;
l++;
r--;
}
}
quickSort(ar, r - ar + 1);
quickSort(l, ar + n - l);
}
error: cannot convert 'int ()[4]' to 'int' for argument '1' to 'void quickSort(int*, int)'
The name of the array is already the address so you do not need the & before myArray.
try this
int myArray[] = {4, 8, 2, 11};
int sortedArray[4];
void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
}
void loop() {
// put your main code here, to run repeatedly:
quickSort(myArray, 4);
for (int i = 0; i < 4; i++)
Serial.println(myArray[i]);
delay(2000);
}
void quickSort(int *ar, int n)
//the local 'ar' variable, through the dereference operator * now
//points to the array that you fed it with the dereference operator &
{
if (n < 2) //array too small
return;
int p = ar[n / 2];
int *l = ar;
int *r = ar + n - 1;
while (l <= r) {
if (*l < p) {
l++;
}
else if (*r > p) {
r--;
}
else {
int t = *l;
*l = *r;
*r = t;
l++;
r--;
}
}
quickSort(ar, r - ar + 1);
quickSort(l, ar + n - l);
}