Sometimes when writing firmware for embedded systems we have to sort lists of numbers or text into numerical or lexical order. To do this we use some kind of sorting algorithm. There are literally dozens of algorithms and variations to choose from, and a whole branch of computer science is devoted to developing new ones and improving old ones. It’s hard to know where to start.
When selecting an algorithm, you have a few variables to consider – speed, computational complexity, and memory requirements – to name just three. I’m going to suggest that in embedded systems you are likely dealing with modest arrays of data (up to a few hundred elements say) and you don’t have a lot of spare RAM for working buffers. In this case you will most likely use one of the simpler sort-in-place algorithms like bubble sort or insertion sort.
These (especially insertion sort) are quite fast for small data sets, have the advantage of low complexity and low memory requirements – they don’t need separate input and output arrays or intermediate storage. The sorting takes place entirely within the data array. You need just a few extra bytes to hold array indices and the like.
Bubble sort is the easiest to understand so we will start there. Figure 1 shows the process conceptually. In this example we are sorting an array of six integers (3, 4, 1, 5, 6 and 3) into ascending order. Starting at the top left of the diagram, we begin with the first element of the array and compare it with the next one. If the first is larger than the second we swap them, otherwise we do nothing. In our example, the elements are 3 and 4 respectively so no swap takes place.
The Bubble Sort algorithm shown here moves builds a sorted array shown in green by successively moving the largest element in the unsorted part of the array to the end. This is one of the simplest algorithms but not the most efficient.
We then move down the diagram to the second element and compare it with the third one in the same way. In this case the elements are 4 and 1 so they are swapped. We keep doing this with each successive element – 4 and 5 (no swap), 5 and 6 (no swap) and 6 and 3 (swap).
This sequence has pushed the highest element in the array to the right-hand end (it has “bubbled” to the top). It is shown shaded green in the diagram. We now repeat the process as shown in the second and subsequent columns, moving the next highest element right, but stopping one place earlier each cycle since the rightmost elements are already sorted.
Eventually we end up with a fully sorted array. You may note that the initial order of the two equal value elements (3 in our case) is preserved in the sorted array. This can be important in some applications. Sorting algorithms that preserve the order of equal-value elements are said to be “stable”.
Implementing bubble sort in code is pretty simple as shown in the code snippet in Figure 2. The outer loop with index i iterates through all the elements (shown horizontally in Figure 1) while the inner loop with index j scans the array checking if a swap is needed. The three lines inside the if statement simply swap the positions of elements A[j] and A[j+1].
Implementing Bubble Sort in C is fairly straightforward as shown here. The inner loop compares adjacent elements and swaps them if necessary to move the largest one up the array.
Bubble sort is simple, buts it does have the disadvantage of requiring us to iterate through all the elements even if the list is not far from sorted to begin with. You can see that in Figure 1 the list is fully sorted with the swap at the bottom of the third column (i = 2, j = 2). The rest of the operations make no further changes to the list. Insertion sort provides a more efficient alternative. Instead of pushing the highest element to the end of the array, it takes each successive unsorted element and inserts it into the sorted part of the array in the right location.
Figure 3 shows how this works. There is no need to sort the first element, since it will always be in the right place in a one-element sorted array! Instead, we start with the second element (i = 1) which has value 4 in our example. If this element is larger than or equal to the element to its left, it is in the right place and can be left alone to expand the sorted part of the array. Otherwise, it must be moved to the correct place in the sorted array.
The Insertion Sort algorithm builds the sorted array shown in green by inserting each successive unsorted element into it at the right location. The existing sorted elements are “shuffled along” to make room for the insertion.
You can see this in action for the third element (i = 2) where it takes two swaps to move the element with value 1 into the correct place within the sorted part of the array shown in green. The nice thing about this algorithm is that it only moves elements as far as is necessary to insert them in the right place. The code for this sorting algorithm in Figure 4 is not much more complex than that for bubble sort. Note that the outer loop indexes the element to insert, and the inner loop shuffles already sorted elements right to make space for it.
Implementing Insertion sort in C is very similar in complexity to bubble sort. The inner loop runs only until the correct location for the element is found. This makes it more efficient than bubble sort for partially sorted lists.
Instead of sorting numbers, we sometimes have to sort strings into lexical (alphabetical) order. This is pretty easy because the C standard library provides a function “strcmp” which does most of the heavy lifting. It compares two strings and returns an integer that is zero if the strings are equal, is positive if the first string is lexically larger than the second or negative if it is smaller.
If you replace the integer comparison with a string comparison you can pretty easily convert an integer sorting algorithm to a string sorting one. Figure 5 shows a complete example program using insertion sort to sort an array of strings and the results of it running in one of the on-line C compilers.
Adapting a sorting algorithm (here Insertion Sort) to sort strings is fairly easy. The C standard library function “strcmp” is used in place of the numerical comparison. The output window on the right shows the unsorted and sorted strings.
Bibliography
“Online C Compiler.” Accessed March 24, 2024. https://www.tutorialspoint.com/compile_c_online.php.
GeeksforGeeks. “Sorting Algorithms,” January 24, 2024. https://www.geeksforgeeks.org/sorting-algorithms/.
Sponsor this Article
Andrew Levido (andrew.levido@gmail.com) earned a bachelor’s degree in Electrical Engineering in Sydney, Australia, in 1986. He worked for several years in R&D for power electronics and telecommunication companies before moving into management roles. Andrew has maintained a hands-on interest in electronics, particularly embedded systems, power electronics, and control theory in his free time. Over the years he has written a number of articles for various electronics publications and occasionally provides consulting services as time allows.
