Lesson 10 – Sorting Algorithms
Sorting algorithms help to improve the organization of data, allowing you to find information faster during searching and improve both memory usage and efficiency in data processing. I would say that close to 90% of software development lies in the realm of data processing and data analytics and 10% is related to hardware drivers, robotics and control systems. So I felt while the focus of the course was on Arduino programming it was important to also cover the broader aspects of programming in general. There are several mainstream sorting algorithms which you can do a google search for an investigate them, but I plan to cover a few of the easier to describe ones here.
If you want to write code for these algorithms, while it is possible on the Arduino IDE it requires using the serial commands to be effective and it is far better to write this on a computer using a standard C++ compiler. You have a couple of different options available depending on if you want to be able run the stuff you write while offline, or just want to see the code work.
If you want to just see the code work, the easiest way to do this is to utilize one of the many free online compilers my two favorite ones are:
- https://www.onlinegdb.com/online_c++_compiler I like this one for the simplicity of use.,
- https://onecompiler.com/cpp I like this one because they have compilers available for many different languages.
As for keeping your code locally and running it on your own computer, while it takes a little more work, is the best option. There are a couple different options
- Microsoft Visual Studio if you are running Windows: You can find it here https://visualstudio.microsoft.com/vs/features/cplusplus/.
- Use X-Code if you are running MacOS you can find it here: https://developer.apple.com/xcode/
- Use a test editor and g++ compilers if you are running Linux. On Ubuntu linux you can install them with “apt install g++” and I personally like vim or emac for editing text files “apt install vim” or “apt install emacs”
Now that we have the tools out of the way lets get down to the Algorithms
Insertion Sort
I like to describe this one by how most people sort cards in the hands when playing card games, you pick up the first card and put it in your hand, you pick up the second card and place it to the left if it is lower or to the right if it is higher. You pick up the third card and place to the left if it is lower than the first card, in the middle if it is higher than the first card, or lower than the second card or in-between if it is higher than the second card. This process continues until you have placed all the cards either at the end or in between the other cards based on their values.
#include <iostream>
#include <vector>
using namespace std;
void printarry(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
void insertionsort(vector<int>& arr, int n) {
for (int i = 1; i < n; ++i) {
printarry(arr);
int key = arr[i];
int j = i - 1;
// move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6};
int n = arr.size();
insertionsort(arr, n);
printarry(arr);
return 0;
}Bubble Sort
This one is fairly easy to describe with cards as well, only in this case you look at two consecutive cards and if the first card is higher than the second you swap them, you repeat this process through the stack of cards an equal number of times as the number of cards and at the end all the cards will be sorted. You can add an extra flag that indicated if any cards were swapped on the last pass and can stop the sort early if no swaps were made which can speed up the algorithm.
#include <iostream>
#include <vector>
using namespace std;
// A function to print an array
void printarray(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// An optimized version of Bubble Sort
void bubbleSort(vector<int>& arr) {
int n = arr.size();
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
printarray(arr);
// If no two elements were swapped, then break
if (!swapped)
break;
}
}
int main() {
vector<int> arr = { 5, 6, 1, 3 };
bubbleSort(arr);
printarray(arr);
}Selection Sort
This one can be described like this. You take a stack of cards in your hand and look through the stack to find the lowest card and place it first. You then make a second pass and find the lowest remaining card and place it second. and so on until you have placed all the cards.
#include <iostream>
#include <vector>
using namespace std;
// A function to print an array
void printarray(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
void selectionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
// Assume the current position holds
// the minimum element
int min_idx = i;
// Iterate through the unsorted portion
// to find the actual minimum
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[min_idx]) {
// Update min_idx if a smaller
// element is found
min_idx = j;
}
}
// Move minimum element to its
// correct position
swap(arr[i], arr[min_idx]);
printarray(arr);
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
printarray(arr);
return 0;
}Counting Sort
The counting sort is not a comparison based sorting algorithm it is more what I would call a stacking sort algorithm. In the counting sort you look through the stack of cards and find the highest and lowest value. Then you create a separate array to store the count of each value. Next you start with the lowest value in the sequence and count the number of cards that match that value and move to the next value, the value can have zero cards in this case. Then you read the count array and write the numbers back into the original array sorted.
So you can think of them like stacking the cards of the same value in piles that are in number order. then picking up all the cards.
#include <iostream>
#include <vector>
using namespace std;
// A function to print an array
void printarray(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
vector<int> countsort(vector<int>& arr) {
int n = arr.size();
printarray(arr);
// find the maximum element
int maxval = 0;
for (int i = 0; i < n; i++)
maxval = max(maxval, arr[i]);
// create and initialize count array
vector<int> count(maxval + 1, 0);
// count frequency of each element
for (int i = 0; i < n; i++)
count[arr[i]]++;
// compute prefix sum
for (int i = 1; i <= maxval; i++)
count[i] += count[i - 1];
printarray(count);
// build output array
vector<int> ans(n);
for (int i = n - 1; i >= 0; i--) {
ans[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return ans;
}
int main() {
vector<int> arr = {2,5,3,0,2,3,0,3};
vector<int> sorted = countsort(arr);
printarray(sorted);
return 0;
}Quick Sort
In the quick sort you chose a pivot point or “card” and then we arrange the list around the pivot recursively. There are different methods to picking the pivot, from always choosing the first element, always choosing the last element, always choosing a random element, or finding the median and using it. The last option while it will always split the array in half each time it actually slows down the sort. The best seems to be picking a random card and the worst is picking the last card if the cards happen to already be sorted. So here is the basic concept. You pick a random card from the pile of cards and split the cards into two piles, cards lower than the pivot and cards higher than the pivot. You repeat this process with each stack of cards until only one card remains in each stack. As you will have stacked the cards below and above the original pivot you can now just pick the single card stacks up in order. This is considered a partitioning algorithm because it splits or partitions the data being sorted until it can’t be partitioned any smaller. The quick sort is still the fastest sort algorithm for computers today.
The key process in quickSort is a partition(). There are three common algorithms to partition. All these algorithms have O(n) time complexity.
- Naive Partition: Here we create copy of the array. First put all smaller elements and then all greater. Finally we copy the temporary array back to original array. This requires O(n) extra space.
- Lomuto Partition: We have used this partition in this article. This is a simple algorithm, we keep track of index of smaller elements and keep swapping. We have used it here in this article because of its simplicity.
- Hoare’s Partition: This is the fastest of all. Here we traverse array from both sides and keep swapping greater element on left with smaller on right while the array is not partitioned. Please refer Hoare’s vs Lomuto for details.
The key process in quickSort is a partition(). There are three common algorithms to partition.
Naive Partition: Here we create copy of the array. First put all smaller elements and then all greater. Finally we copy the temporary array back to original array. This requires O(n) extra space.
Lomuto Partition: I used this partition in this article. This is a simple algorithm, we keep track of index of smaller elements and keep swapping. I used it here in this article because of its simplicity.
Hoare’s Partition: This is the fastest of all. Here we traverse array from both sides and keep swapping greater element on left with smaller on right while the array is not partitioned. Please refer Hoare’s vs Lomuto for details.
#include <iostream>
#include <vector>
using namespace std;
// A function to print an array
void printarray(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int partition(vector<int>& arr, int low, int high) {
// choose the pivot
int pivot = arr[high];
// undex of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;
// Traverse arr[low..high] and move all smaller
// elements on left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// move pivot after smaller elements and
// return its position
swap(arr[i + 1], arr[high]);
return i + 1;
}
// the QuickSort function implementation
void quickSort(vector<int>& arr, int low, int high) {
cout << "low:" << low << " high:" << high <<" arr:";
printarray(arr);
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
printarray(arr);
return 0;
}
