Go Down

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

robtillaart


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 Sort
bubbleSort:   49992
shellSort:    36376
insertSort:   21928
combSort11:   4728
quickSort:    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


Quick RAM investigation - UNO, IDE 1.5.4


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


QUICKSORT

memory before:  1483
lowest memory:  1387
--------------------------
Max RAM used:    96 bytes


COMBSORT11
memory before:  1483
lowest 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

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 Sort
bubbleSort:     1167696
bubbleFlagSort: 1203072
shellSort:      1228124
insertSort:     636660
combSort11:     36504
quickSort:      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 am Last 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

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

Confirm your email address

We need to confirm your email address.
To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy