Bubble Sort

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});