Bubble Sort

Introduction

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly compares and swaps adjacent elements if they are in the wrong order. This process continues for multiple passes until the entire array is sorted, with the largest elements progressively "bubbling up" to their correct positions. While simple to implement, Bubble Sort is inefficient for large datasets due to its high time complexity.

How Bubble Sort Works?

Multiple Passes:

Bubble Sort uses several passes through the array to sort it. In each pass, the largest unsorted element "bubbles" to the correct position at the end of the array.

Placing Elements in Correct Positions:

• After the first pass, the largest element is in its correct position (the last element of the array).
• After the second pass, the second-largest element is in its correct position (second-to-last element), and so on.

Reducing the Range:

• After each pass, the range of unsorted elements decreases. Only the unsorted part of the array is considered for swapping in the next pass.
• After k passes, the largest k elements are guaranteed to be in their correct positions at the end of the array.

Comparison and Swapping:

• In each pass, the algorithm compares adjacent elements and swaps them if the larger element is before the smaller one.
• This ensures that, after every pass, the largest remaining element is placed in its correct position.

Early Termination:

• If a pass completes without any swaps, the algorithm terminates early, as the array is already sorted.

Implementation of Bubble Sort

// bubblesort.cpp
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int> &arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; i++)
{
    for (int j =0; j < n - i - 1; j++)
    {
        if (arr[j] > arr[j + 1])
        {
            swap(arr[j], arr[j + 1]);
        }
    }
}
}
int main()
{
vector<int> arr{9, 5, 4, 1};
bubbleSort(arr);
for (int &ele : arr)
{
    cout << ele << " ";
}
}

Time Complexity

• Best Case:O(n), When the array is already sorted or nearly sorted.
• Average Case:O(n*n), When the array is in random order.
• Worst Case: O(n*n),When the array is sorted in descending order.

Space Complexity

• Constant Space:O(1)
• Space Complexity:O(1)