Bubble Sort

Reading time ~1 minute

Bubble sort is a sorting algorithm that iterates through an array, comparing two elements at a time and swapping if appropriate. On each pass, at least one value is placed in its final sorted location (though it is possible that more are also placed in their final location).

Big-O Notation: Because the array must be iterated over one time for every element in the array, the average runtime would be quadratically proportional to the length of the array. This means that the average runtime complexity is expressed as .

The following implementation of the bubble sorting algorithm is written in C# with a generic implementation that makes use of the IComparable interface so that any array containing an object that implements this interface can be sorted (integers, strings, characters, etc…)

public class BubbleSorter<T> where T : IComparable<T>
{
    public T[] Sort(T[] array)
    {
        bool swapFound;
        do
        {
            swapFound = false;
            
            // used to track the earliest point in the array that is fully sorted
            var firstSortedElement = array.Length;
            for (var i = 0; i < firstSortedElement - 1; i++)
            {
                var comparison = array[i].CompareTo(array[i + 1]);
                if (comparison > 0)
                {
                    swapFound = true;
                    firstSortedElement = i + 1;
                        
                    var temp = array[i + 1];
                    array[i + 1] = array[i];
                    array[i] = temp;                
                }
            }
        } while (swapFound);

        return array;
    }
}

In order to make use of this class, you would do something like the following:

var bubbleSorter = new BubbleSorter<int>();
var result = bubbleSorter.Sort(new[] {9, 5, 1, 4, 2, 8, 2});

Software Interfaces in the Wild

Interfaces are a powerful tool when used properly. This article explores a real-world example. Continue reading

Microservices are not Micro; They are Vertical

Published on October 16, 2018

Giving Life to Legacy Apps with Docker

Published on October 07, 2018