Sorting Algorithms

Often we require data to be ordered according to some criteria but how do we sort the data? This has been an active area of research for decades. Here I compare a few of the more well known algorithms.

Bubble Sort

I think I was in secondary school when I first encountered a sorting algorithm, as part of a computer studies class project we had to implement one.

Bubble sort was the one that was chosen (I can’t remember if it was the teacher or our choice). It’s quite a simple algorithm that “bubbles” up the smallest element of an array towards the top.

Starting at the top of the array compare adjacent elements and swap them if they are in the wrong order (first element is greater than the next one). This process is repeated until all elements are in their correct order.

Here is an implementation in C

void bubble_sort(int *data, int num_items)
{
    int items_swapped;
    
    do
    {
        items_swapped = 0;

        for (int i = 1; i < num_items; i++)
        {
            if (data[i-1] > data[i])
            {
                int temp = data[i-1];
                data[i-1] = data[i];
                data[i] = temp;
                
                items_swapped = 1;
            }            
        }
    } while (items_swapped != 0);
}

Bubble sort is quite naive and performs badly in many cases. A simple inspection of the above function shows that it will execute the outer loop until the inner loop has made no swaps. This means that when the data is completely sorted, one more iteration of the outer loop will be executed.

In the degenerate case when the data to be sorted is in reverse order (i.e. sorted from high to low), it would take \( n \) iterations of the outer loop, for each of these will require n iterations of the inner loop ( \(n \times n \ or \ n^2\) operations).

We say that the performance of the algorithm is \(O(n^2)\).

Big O notation is a way of expressing the relative performance of an algorithm in terms of the number of operations it will take.

We can see how the sort progresses in the average case in the diagram below. Each row is one iteration of the outer loop. The color indicates the value of each element in the array.

Initially the data is randomly arranged but after each iteraton it becomes gradually arranged in similar color order. At the end the color transition between elements is smooth, indicating a smoothed ordered set of data.

So now that we know the performance of bubble sort can we do any better?

Selection Sort

Selection sort works by finding the smallest element in the array and exchanging it with the first one. This first element is now in it’s correct place and the search resumes for the next smallest element, starting from the next element of the array.

In this way the array is partitioned into two sections. Everything before the current search postion start is sorted and everything else is (potentially) unsorted. The sorted section grows until it covers the whole of the array, the data is then sorted.

Here is an implementation in C

void selection_sort(int *data, int num_items)
{
    for (int i = 0; i < num_items; i++)
    {
        int min = i;
        
        for (int j = i+1; j < num_items; j++)
        {
            if (data[j] < data[min])
            {
                min = j;
            }
        }
        
        int temp = data[min];
        data[min] = data[i];
        data[i] = temp;
    }
}

As the sorted portion of the array grows for each iteration of the outer loop, the search space covered by the inner loop reduces, the perfomance is approximately \(O(n + (n-1) + (n-2) + … + 1)\). Also the inner loop is considerably simpler than bubble sort loop.