Bubble Sort also known as Sinking sort. It is the easiest sorting algorithm. Bubble sort compares adjacent elements from left to right and swaps them if they are out of order.

By Swfung8 - Own work, CC BY-SA 3.0, commons.wikimedia.org/w/index.php?curid=149..

How does it work ?

Here are the steps the algorithm would follow.

1. Start with the first element.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, then swap both the elements. If not, move to the next element.
4. Repeat steps 1 – 3 until we get the sorted list.

Take an array of numbers " 5, 3, 4, 2", and sort the array from lowest number to greatest number using bubble sort.

The steps to sort this list would involve –

First Pass

(5,3,4,2) → (3,5,4,2)

(3,5,4,2) → (3,4,5,2)

(3,4,5,2) → (3,4,2,5)

Second Pass

(3,4,2,5) → (3,4,2,5)

(3,4,2,5) → (3,2,4,5)

(3,2,4,5) → (3,2,4,5)

Third Pass

(3,2,4,5) → ( 2,3,4,5)

(2,3,4,5) → (2,3,4,5)

(2,3,4,5) → (2,3,4,5)

In bubble sort, to sort a list of size n, we need to perform n – 1 iterations.

Time complexity

The time complexity of bubble sort is O(n^2)

Worst case performance : O(n^2) , when we want to sort a list in ascending order, but it is arranged in descending order.

Average case performance : O(n^2) . When the list is in random order.

Best case performance : O(n) . When the list is already in sorted order.

Bubble sort in c#

static int[] bubbleSort(int[] input)
{
    var length = input.Length;

    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length -1  ; j++)
        {

            if (input[j] > input[j + 1])
            {
                (input[j], input[j + 1]) = (input[j + 1], input[j]);
            }
        }
    }
    return input;
}