Sort Algorithms
The four classic programming algorithms featured in this chapter are worth the time taken to study them. The code samples are succinct and include some good practice with pointers towards the end.
As Arduino board capacities increase, new applications will inevitably collect greater quantities of data that will need to be manipulated. One fundamental tool that should be added to any programmer’s box of tricks is the ability to sort an array of values.
Here is a handy test rig for the three sort algorithms we will be exploring first:
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
bubbleSort(array, 12);
//shellSort(array, 13);
//quickSort(array, 0, 12);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
The Bubble Sort
Even a relative newcomer to programming could probably figure out a sort routine akin to the simplest of sort algorithms, the bubble sort. It is included here because it is a great introduction to the topic although now rarely used as it is very slow when applied to a disordered array. However, it does have some residual utility in that rare circumstance when you know an array will be very nearly already in the desired order. You might just use it then and ignore any derision from fellow programmers who will have missed that vital performance factor.
The bubble sort simply loops through the array checking the value of each element against the next one in the array. If they are out of order then they are swapped. The algorithm is complete when a loop through the array finds no values out of order. Sweet and simple.
void bubbleSort(int array[], int lastElement) {
bool swap = true;
int hold;
while (swap) {
swap = false;
for (int i = 0; i < lastElement; i++) {
if (array[i] > array[i + 1]) {
swap = true;
hold = array[i];
array[i] = array[i + 1];
array[i + 1] = hold;
}
}
}
}
You get way more programmer street cred with the following two sort algorithms.
The Shell Sort
The Shell sort is named after it’s inventor D. L. Shell. I have been a longstanding fan of the Shell sort and used it to sort a great many different types of data structure using many different programming languages over the years.
Instead of comparing adjacent elements like the bubble sort, the Shell sort starts by comparing elements that are far apart in the array. This quickly reduces the overall disorder as the gap between the compared elements reduces in steps to 1.
void shellSort(int array[], int arrayLength) {
int temp;
for (int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >= 0 && array[j] > array[j + gap];
j -= gap) {
temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
The Quick Sort
Then we have the Quick Sort algorithm created by C. A. R. Hoare. This algorithm uses recursion. Recursion is where a function calls itself, usually to process a sub-set of data. The quick sort code is compact and runs quickly although there is the overhead of creating values on the stack to support the recursive calls to itself and to the abstracted swap() utility function.
The quick sort divides the array into two subsets (designated by a pair of array element index values). One subset has values less than a selected element and the other those greater (or equal). The process is repeated recursively for the two subsets until a subset is found to have less than two elements in it. Once that state arises, then the algorithm can back up to the previous level.
// quick sort - uses a helper function swap()
// and calls itself recursively
void quickSort(int array[], int left, int right) {
if (left >= right) { return; } //do nothing if < 2 elements
swap(array, left, (left + right) / 2);
int last = left;
for (int i = left + 1; i <= right; i++) {
if (array[i] < array[left]) {
swap(array, ++last, i);
}
}
swap(array, left, last);
quickSort(array, left, last - 1);
quickSort(array, last + 1, right);
}
void swap(int array[], int elem1, int elem2) {
int hold = array[elem1];
array[elem1] = array[elem2];
array[elem2] = hold;
}
There is an implementation of the quick sort algorithm in stdlib.h called qsort() where you can supply your own comparison function which facilitates sorting different data types. We will explore this library function later in this chapter as it is an excellent example of how to implement a generic function that can provide a service (in this case sorting the values in an array) for different data types.
Could we improve the code in our sorts?
XOR Integer Swap
We can explore a process that uses xor to swap the values of two integers without using a third int variable. This is a simple three step process but to see what is going on we should probably use two example variables.
First a quick refresher on the xor operator:
| a | b | a^b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
If one or other of the bits in a given position within two integer variables is set on then the xor result will have the bit set on. If neither bits is on or of both are set on then the xor result will have the bit set 0.
Now a worked xor swap example
| We are swapping the values in two int variables a and b | ||
| Step | Example | |
| a = 45 b = 126 |
a = 0010 1101 b = 0111 1110 |
|
| a ^= b; (shorthand for a = a ^ b) |
a = 0101 0011 b = 0111 1110 |
|
| b ^= a; | b = 45 | a = 0101 0011 b = 0010 1101 |
| a ^= b; | a = 126 |
a = 0111 1110 magic! |
There is an arithmetic version of this process shown using the same two initial values.
| a=a+b | a==171 |
| b=a-b | b==45 |
| a=a-b | a==126 |
The arithmetic technique works fine for negative as well as positive numbers as well as large values approaching the limits for a given integer variable. If you need convincing, write a short test program and output the binary representation of the numbers as this short algorithm progresses. Asking how to swap the values of two integer variables without using a third variable is a great programming puzzle. This arithmetic solution is easy to prove on a beer mat even after a few adult beverages.
There is one big caveat when using the xor technique to swap two integers in an array (say swap array[x] with array[y]). It is vital that the index values x and y are never equal. If x and y reference the same element, then that element will be zeroed.
We could apply the xor swap to any of the sort algorithms but here is a version of the swap() function used by the quick sort that uses the technique. Based on this you should be able to apply it should you wish in any code that swaps integer values.
void xorSwap(int array[], int a, int b){
if(a != b) {
array[a] ^= array[b];
array[b] ^= array[a];
array[a] ^= array[b];
}
}
Sort Order
The three sorts featured so far have been used to sort an array of int values into ascending order where the lowest integer value ends up in the first array element and the largest value arrives in the last array element. There are often occasions when sorting an array into the opposite (descending) order would be appropriate. One strategy to achieve that might be to write a function to reverse the order of a sorted array. Alternately, we could rewrite our sort functions to sort in either direction based upon an additional argument.
Reverse An Array
The following program uses the shell sort from above (but not shown so don’t forget to include it) and demonstrates the first idea where the sorted array is reversed. Almost all of the work in the reverseArray() function is done by the ‘for loop’ statement. Notice that variable i is incremented and variable j is decremented in the third component of that for statement.
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
shellSort(array, 13);
reverseArray(array, 12);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
void reverseArray(int array[], int lastElement) {
for(int i = 0, j = lastElement; i < j; i++, j--) {
xorSwap(array, i, j);
}
}
void xorSwap(int array[], int a, int b){
if(a != b) {
array[a] ^= array[b];
array[b] ^= array[a];
array[a] ^= array[b];
}
}
Set Sorting Order
The second approach to setting the sort order makes use function overloading to support a default sort order of ascending. The sample code concentrates on the shell and quick sort algorithms and has them sharing a common xorSwap() function.
void shellSort(int array[], int arrayLength) {
shellSort(array, arrayLength, ASC);
}
void shellSort(int array[], int arrayLength, Sort_Order so) {
for(int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >=0 && ((so == ASC) ? array[j] >
array[j + gap] : array[j] < array[j + gap]); j -= gap) {
xorSwap(array, j, j + gap);
}
}
}
}
void xorSwap(int array[], int a, int b){
if(a != b) {
array[a] ^= array[b];
array[b] ^= array[a];
array[a] ^= array[b];
}
}
void quickSort(int array[], int lastElement) {
quickSort(array, 0, lastElement, ASC);
}
void quickSort(int array[], int lastElement, Sort_Order so) {
quickSort(array, 0, lastElement, so);
}
void quickSort(int array[], int firstElement, int lastElement){
quickSort(array, firstElement, lastElement, ASC);
}
void quickSort(int array[], int firstElement, int lastElement,
Sort_Order so){
if(firstElement > lastElement) { return; }
xorSwap(array, firstElement, (firstElement + lastElement) / 2);
int last = firstElement;
for(int i = firstElement + 1; i <= lastElement; i++) {
if((so == ASC) ? array[i] < array[firstElement] : array[i] >
array[firstElement]) {
xorSwap(array, ++last, i);
}
}
xorSwap(array, firstElement, last);
quickSort(array, firstElement, last - 1, so);
quickSort(array, last + 1, lastElement, so);
}
Try those with a test setup() function where each commented out option can be run in turn:
enum Sort_Order {ASC, DESC};
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
shellSort(array, 13, DESC);
//shellSort(array, 13);
//quickSort(array, 12);
//quickSort(array, 0, 12, ASC);
//quickSort(array, 12, DESC);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
As you can see, the sort algorithms are using the ternary operator (?) to apply the appropriate comparison test based upon the Sort_Order enum setting.
The Arduino library support for the quicksort algorithm is explored a little later in this chapter but there, the approach is to pass a function that manages the array element comparisons into the sort process. This makes it possible to write a sort function that can handle a wide range of data types but also allows the programmer to set the sort order. We could try that approach with the shell sort.
If two alternate comparison functions were created:
int compIntAsc(int a, int b) {
if (a == b) {return 0;}
return (a < b) ? -1 : 1;
}
int compIntDsc(int a, int b) {
if(a == b) {return 0;}
return (b < a) ? -1 : 1;
}
They could be selectively passed to a modified shell sort function to sort the array into the desired order. The three possible return values (-1, 0 and 1) from the compare functions are standard practice and you will bump into this pattern in lots of code.
There is an additional shellSort argument that is a pointer to a function that takes two int arguments and returns an int value, which is the signature for the two compare functions above. You knew that pointers would sneak in here somehow.
void shellSort(int array[], int arrayLength, int* cmp(int, int)) {
int temp;
for (int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >= 0 && cmp(array[j], array[j + gap])
== 1; j -= gap) {
xorSwap(array, j, j + gap);
}
}
}
}
If you remember to include our xorSwap function then this can be tested with a short test setup() function like:
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
//shellSort(array, 13, compIntAsc);
shellSort(array, 13, compIntDsc);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
That was a good reminder that a function’s name is the name of a pointer to itself.
Sorting Non-Numeric Data
Sorting integers is one thing but a competent C programmer may also have to tackle the task of sorting an array of strings – each being a null terminated char array. In this exercise, I have tackled the task of sorting an array of words into alphabetical order. Sorting these words needs to take into account the fact that the individual char arrays (strings) will have different lengths and that some strings may only differ towards their ends.
Inevitably, given the memory limitations of current Arduinos like the Uno, this exercise is somewhat artificial. It may be that lines of text from a file held on an SD “drive” need to be sorted or that string data has been collected from another source. So that I can be sure that the code will run on a basic Arduino this program simply uses some string constants. (see the later chapter on Optimising SRAM) These string constants are then accessed using an array of pointers to those char arrays.
Assuming that we are using a quick sort algorithm then we are going to need a process to compare two strings and another to swap the pointers in any two elements of the pointer array. We could farm both out to distinct functions. We should also, I would suggest, make some provision for dealing with alphabetic case.
Are we going to sort with a == A or a > A (as the ASCII code would have it)?
A full program to sort a set of strings follows. Variations in letter case and the duplication in the words to be sorted are deliberate and designed to test the options.
const char w1[] = "autocracy";
const char w2[] = "democracy";
const char w3[] = "Democrat";
const char w4[] = "oligarchy";
const char w5[] = "autocrat";
const char w6[] = "aristocrat";
const char w7[] = "bureaucracy";
const char w8[] = "technocrat";
const char w9[] = "oligarch";
const char w10[] = "matriarch";
const char w11[] = "Reservoir";
const char w12[] = "squash";
const char w13[] = "matriarch";
char* wordArray[] = {w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11,
w12, w13};
void setup() {
Serial.begin(115200);
wQSort(wordArray, 0, 12, true);
for(int i = 0; i < 13; i++){
Serial.println(wordArray[i]);
}
}
// the quick sort function looks like you would expect
// with an added ignoreCase argument
void wQSort( char* array[], int left, int right, bool ignoreCase) {
if(left > right) {return; }
swap(array, left, (left + right) / 2);
int last = left;
for(int i = left + 1; i <= right; i++) {
if(compStr(wordArray[i], wordArray[left], ignoreCase) < 0) {
swap(array, ++last, i);
}
}
swap(array, left, last);
wQSort(array, left, last - 1, ignoreCase);
wQSort(array, last + 1, right, ignoreCase);
}
// the swap only swaps the pointers – the strings are untouched
void swap( char* array[], int a, int b) {
char * temp = array[a];
array[a] = array[b];
array[b] = temp;
}
// the comparison loops through the two strings until
// there is a difference or one ends
int compStr( char* a, char* b, bool ignoreCase) {
for(; (ignoreCase) ? (tolower(*a) == tolower(*b)) : (*a == *b);
a++, b++) {
if(*a == '\0' || *b == '\0') { // end of one of the strings
if(*a == *b) {return 0;} // both words the same
break;
}
}
// return the difference between the char ASCII codes
return (ignoreCase) ? tolower(*a) - tolower(*b) : *a - *b;
}
That’s an interesting for loop. The first section is empty and the second section uses two different tests based upon the ignoreCase Boolean. It could be changed to a while loop but this one underlines the flexibility available to the programmer.
[N.B. The tolower() function used in the string comparison when case insensitivity is required returns an int value which is the ASCII value of the lower case version of the character. This can of course be cast back to a char.]
The same technique can be used to sort any non-integer data structure – say an array of struct types. For any complex data type (such as a struct) then multiple data elements within two given types might need to be compared to decide upon an ordering. Just as in the string sort above where multiple individual chars within any given string were compared until a difference (if any) was detected. If the array being sorted is a pointer array then no modification might be needed to the main sort function (although alphabetic case might not be a factor). All that would be needed was an alternate compare function that could inspect the elements within a given data structure. You will come across some code later in the book that sorts an array of structs.
Library support for quicksort
Which nicely brings us to the Arduino IDE library implementation of the quicksort algorithm which can handle multiple data types. Current versions have a range of inbuilt value swap capabilities but you do need to supply a compare function. The compare function is passed two void pointers to the array elements to be compared. The programmer needs to pass in a pointer to the prepared comparison function to the qsort() function to enable it to be called when required.
You might like to execute an Internet search for the qsort.c file and take a look at the overall structure of the source code. This includes mechanisms used to manage array element swaps for alternate data types. Also, take a look at the line defining the qsort function itself. Note that the array element to be sorted is represented as a void pointer (which avoids having to define the variable type) and the final argument which defines a comparison function which returns an int.
int (*cmp)(const void *, const void *)
Here is a comparison function that you might supply for a long data type (note the casts from a void pointer to a long pointer):
int lComp(const void *a, const void *b) {
if (*(long*)a < *(long*)b) { return -1; }
if (*(long*)b < *(long*)a) { return 1; }
return 0;
}
The full list of arguments to the qsort function is as follows:
First the array to be sorted, then the length of the array, then the size of the individual array elements and finally the comparison function. The array element size is required as the qsort() function is being passed a void pointer to the array and thus can’t use pointer arithmetic to address individual array elements as pointer arithmetic needs to know what data type the pointer is being applied to.
Optionally switching the sort into a descending order requires a second or different comparison function that reverses the ascending order test. Program code can then pass the appropriate comparison function to qsort() as required.
Here is a short test program that runs the built in qsort().
void setup() {
Serial.begin(115200);
long lArray[] = {764, 123, 9854, 3, 999, 97, 6, 78, 123, 0, 5};
qsort(lArray, 11, sizeof(long), lComp);
for (int i = 0; i < 11; i++) {
Serial.println(lArray[i]);
}
}
int lComp(const void *a, const void *b) {
if(*(long*)a < *(long*)b) {return -1;}
if(*(long*)b < *(long*)a) {return 1;}
return 0;
}
Binary Search
What can we do with our newly ordered data sets? Well one thing that has proven useful over the years is search. Does the array contain a particular value?
Our search could just start at the beginning of the array, checking each value until the required value was found or the process reaches the end of the array. For a large array, this could take some time (at least measured using the timescales of our Arduino microprocessor). As the array is ordered then we could also check to see if the value in a given position in the array was larger than our search term and exit without checking all of the values when what we are looking for is not present in the array. On average, over many searches, we would probably end up checking half of the array values.
The binary search algorithm (sometimes called a binary chop) is much faster. The idea is that the first element of a sorted array to be checked is the middle one. Now, if the middle array value is greater than the one we are searching for we can then check the value half way between the start and that middle value. Of course, if the middle array value proved to be less than the one we were looking for then we could check the value half way between the middle element and the last element. Each time an array element is inspected then (if it is not the one we are looking for) the process would repeat. This continuous splitting of the array into two notional sub parts gives the algorithm its name.
Let us consider the implications of this approach. Suppose we started with an array to be searched containing 100,000 elements (perhaps slightly fanciful in early 2018 but an Arduino with multiple gigabytes of SRAM could be just around the corner). An exhaustive search from the beginning would (on average) require the process to check 50,000 elements and on a bad day rather more. Our binary search process would start with the middle element and (as an example) might have found that value to be larger than the one sought. So, the next element checked would be half way between the start and middle. If that one were too small then the next element checked would be half way between that point and the middle. With just three array elements checked so far, the process would already have eliminated seven eighths of that 100,000. The process should be complete (success or failure) after checking a maximum of 17 array elements (log2 of array length). That is a minimum of 2,941 times faster than the average result from an exhaustive search.
The code is as short as the explanation.
int binarySearch(int array[], int arrayLength, int target) {
int low = 0;
int high = arrayLength - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = array[mid];
if (midVal < target) {
low = ++mid;
} else if(midVal > target){
high = --mid;
}
else {
return mid; // found it
}
}
return -1; //not found
}
There is a nice historical note to add on this venerable and long used algorithm. The line that currently reads:
int mid = (low + high) >> 1;
for years read something like
int mid = (low + high) / 2;
but in 2006 a code wizard called Josh Bloch detected a circumstance where the original code could result in an integer overflow. Thus, the code was revised to use a bit shift.
Even code that has run for decades on countless computers can prove to have a bug when a particular edge case turns up.
Review
When faced with a sequence of data driven tasks, it is always a good idea to consider the data order. Reordering a list can often simplify the required code – sometimes dramatically.
At this stage in the learning process, a programmer looking to enhance his or her skills will be starting to research the software tools available in the standard Arduino libraries and also looking to accumulate a small stock of functions and algorithms likely to be used repeatedly into the future.