Go Down

### Topic: some sorting algorithms compared (Read 240 times)previous topic - next topic

#### robtillaart

##### Nov 21, 2014, 09:38 am

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.
Code: [Select]
`////    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--;    }  }}`

output
`Start SortbubbleSort:   49992shellSort:    36376insertSort:   21928combSort11:   4728quickSort:    3260`

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.

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

#### robtillaart

#1
##### Nov 21, 2014, 11:59 am

Quick RAM investigation - UNO, IDE 1.5.4

Reverse sorted array of 250 values  (to enforce worst case behavior quickSort)

`QUICKSORTmemory before:  1483lowest memory:  1387--------------------------Max RAM used:    96 bytes COMBSORT11memory before:  1483lowest memory:  1462--------------------------Max RAM used:    21 bytes `

So quicksort does not use much memory in absolute sense, but relative to CombSort11 it is about 4.6 times as much.

note: redo timing test with array size above 255.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

#### robtillaart

#2
##### Nov 21, 2014, 01:12 pm
redid the test with array of 1500 elements (+ bit optimized combsort11 + added bubblesort)

Code: [Select]
`////    FILE: sort.ino//  AUTHOR: Rob Tillaart// VERSION: 0.1.01// PURPOSE: compare some sorting methods//    DATE: 2014-11-20//     URL://// Released to the public domain//// #include <FreeRam.h>uint8_t array[1500];uint32_t start;uint32_t stop;uint32_t fr = 2222;void testSort( void(*sf)(uint8_t *, uint16_t), uint16_t sz, char *name){  randomSeed(1);  for (uint16_t i=0; i<sz; i++) array[i] = random(256);  start = micros();  sf(array, sz);  stop = micros();  Serial.print(name);  Serial.print("\t");  Serial.println(stop-start);  //  for (uint16_t i=0; i< sz; i++)  //  {  //    Serial.print(array[i]);  //    Serial.print(" ");  //    if (i%10==0) Serial.println();  //  }  Serial.println();}void setup() {  Serial.begin(115200);  Serial.println("Start Sort\n");  testSort(bubbleSort, 1500, "bubbleSort");  testSort(bubbleFlagSort, 1500, "bubbleFlagSort");  testSort(shellSort, 1500, "shellSort");  testSort(insertSort, 1500, "insertSort");  testSort(combSort11, 1500, "combSort11");  testSort(quickSort, 1500, "quickSort");  //  Serial.println("QSORT RAM:\t");  //  Serial.println(fr);  //  Serial.println("RAM:\t");  //  Serial.println(freeRam());}void loop() {}void bubbleFlagSort(uint8_t * ar, uint16_t n){  // bubble sort with flag  for (uint16_t i=0; i< n-1; i++)  {    bool flag = true;    for (uint16_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 bubbleSort(uint8_t * ar, uint16_t n){  // bubble sort with flag  for (uint16_t i=0; i< n-1; i++)  {    for (uint16_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;      }    }  }}void shellSort( uint8_t *ar, uint16_t n){  uint16_t i, temp;  uint8_t flag = 1;  uint16_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, uint16_t n){  uint16_t i, j;  uint16_t gap;  uint8_t swapped = 1;  uint8_t temp;  gap = n;  while (gap > 1 || swapped == 1)  {    if (gap > 1)    {      gap = gap * 10/13;      if (gap == 9 || gap == 10) gap = 11;    }    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, uint16_t n) {  if (n < 2)  {    // uint32_t s = freeRam();    // if (fr > s) fr = s;    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, uint16_t n){  uint16_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--;    }  }}`

output
`Start SortbubbleSort:     1167696bubbleFlagSort: 1203072shellSort:      1228124insertSort:     636660combSort11:     36504quickSort:      22800`

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

RAM QUICKSORT

memory before:  225
lowest memory:  21
--------------------------
Max RAM used:   204 bytes   (that's 10% of UNO's RAM)

(OK enough played today
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

#### pYro_65

#3
##### Nov 22, 2014, 07:02 amLast Edit: Nov 22, 2014, 07:03 am by pYro_65
Using mega + older Arduino IDE compiler:
Quote
bubbleSort   1167760
bubbleFlagSort   1203144
shellSort   1228200
insertSort   636692
combSort11   36512
quickSort   22876
Using a mega on the new compiler:
Quote
bubbleSort   1202792
bubbleFlagSort   1238100
shellSort   1435748
insertSort   672680
combSort11   42624
quickSort   22492
Strange huh? All got slower except quickSort.

#### robtillaart

#4
##### Nov 22, 2014, 11:00 am
Good and important observation,  ~15% slower

how about the code size generated by the two compilers?
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up

Please enter a valid email to subscribe