Bubble Sort Algorithm

Bubble sort is a simple comparison-based sorting algorithm. It is named like that because it sorts elements similar to the water bubble rising to the surface, i.e. after all iterations are completed, either lower or higher values bubble up towards the top index of the given array.

By making multiple passes through an array with n elements, each pair of adjacent elements is compared one by one based on their values and swapped if they are not in order. They can be sorted in ascending or descending order. The iterations through the array are repeated until there are no swaps needed, which indicates that it is sorted.

The description of the algorithm can be summarized in a tabular form as shown below:

The array will be sorted in n-1 iterations, where n is the total number of elements in it.

Example in C#:

using System;

public class BubbleSort
{    
    public void Main(string[] args)
    {
    int[] arr= new int[100];
    int n, i, j, swap;

    Console.WriteLine("Enter number of elements:");
    n = int.Parse(Console.ReadLine());

    Console.WriteLine("Enter integers:", n);

    for (i = 0; i < n; i++)
        arr[i] = int.Parse(Console.ReadLine());

    for (i = 0 ; i < n - 1; i++)
    {
        for (j = 0 ; j < n - i - 1; j++)
        {
        if (arr[j] > arr[j+1]) /* For descending order you can use < */
        {
            swap     = arr[j];
            arr[j]   = arr[j+1];
            arr[j+1] = swap;
        }
        }
    }

    Console.WriteLine("Sorted list:");

    for (i = 0; i < n; i++)
        Console.WriteLine(arr[i]);
    }
}

Bubble sort can be optimized by adding a flag variable that exits the loop once the swapping is done. The variable will hold 1 (true) if there is swapping and if there isn’t it will break out the for loop and save time.

Optimized example in C#:

using System;

public class BubbleSort
{
    public void Main(string[] args)
    {
    int[] arr= new int[100];
    int n, i, j, swap;
    bool flag = false;

    Console.WriteLine("Enter number of elements:");
    n = int.Parse(Console.ReadLine());

    Console.WriteLine("Enter integers:", n);

    
    for (i = 0; i < n; i++)
        arr[i] = int.Parse(Console.ReadLine());

    for (i = 0 ; i < n - 1; i++)
    {
        for (j = 0 ; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j+1]) /* For descending order you can use < */
            {
                swap = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = swap;
                flag = true;
            }
            if (flag == false)
            {
                break;
            }
        }
    }
   
    Console.WriteLine("Sorted list:");

    for (i = 0; i < n; i++)
        Console.WriteLine(arr[i]);
    }
}

This algorithm is used mainly as an example for educational purposes because it is fairly easy to understand and implement but it is not practical due to its average-case complexity of O(n²) and worst-case complexity of O(n²).  For example, quicksort and heap-sort are faster sorting algorithms. Note that the best-case time complexity for the bubble sort algorithm will be O(n) only if the array is already sorted. It requires only a single additional memory space for the temporary variable to facilitate swapping, hence the space complexity for this algorithm is O(1). In the optimized algorithm, the flag variable adds to the space complexity thus, making it O(2).