# 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).

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