So far, in our programming series, we have learned the basics of writing computer programs in C, and we’ve discussed some good and bad practices in programming. We have acquainted ourselves with data types, operators, input / output and the technique of writing functions.
Now it is time to study some common groups of algorithms—well known ways of solving well known problems. Some of these things may seem complicated and hard to understand in the beginning, but as you advance and use them often, you will notice that you are writing them almost automatically. We will also be explaining some new data structures like stacks, priority queues, linked lists etc. which are often used in combination with these most common algorithms.
The first group we will discuss—sorting algorithms—is probably the simplest to comprehend, because it is easy to see how they’re applied in real life. The problem of sorting a data structure—most often an array, is so common that there are hundreds of algorithms to solve it, ranging from quite simple, to complex ones like quicksort.
We will explain the two simplest (in the author’s opinion) sorting algorithms, called selection sort and bubble sort.
This algorithm divides the input array into two parts: the sub-array of items already sorted, and the sub-array of items remaining to be sorted that occupy the rest of the array. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sub-array, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sub-array boundaries one element to the right. Simply speaking, in each iteration it finds the minimum element (if the sorting order is increasing) and puts it in the beginning of the array, by exchanging its place with other elements.
Here is the code in C for selection sort on an array of n elements:
for (int i=0; i< n-1; ++i)
for( int j=i+1; j<n;++j)
if(array[i] > array[j])
int temp = array[i];
The code segment after the if statement is usually called swapping, and we will be using it in bubble sort, too. The swapping is necessary because, if we simply wrote
array[i] = array[j];
we would lose the value of array[i] after this line executes, and then wouldn’t be able to exchange the values of the two elements, which we are trying to do. That is why an additional variable is used to temporarily store the result of array[i].
Bubble sort is similar to selection sort in matters of complexity, and the need to exchange the values of certain elements. But it is important to notice the difference: selection sort will compare the i-th element with the i+1, i+2 … n-th element of the array, while bubble sort will always compare two subsequent elements, and swap them if needed.
Here is the code for bubble sort:
for (int i=1; i< n-1; ++i)
for( int j=0; j<n-1-i;++j)
if(array[j] > array[j+1])
int temp = array[j];
These were some common and simple sorting algorithms, used mostly on small arrays and lists. Next time we continue with useful programming lessons, so make sure you stay tuned!