Bubble Sort Algorithm

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Detailed Steps

1. Start at the first element of the array.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next element and repeat the comparison until the end of the array.
5. After each pass, the largest element among the unsorted portion "bubbles up" to its correct position.
6. Repeat the passes until no swaps are needed in a complete pass (the array is sorted).

Time and Memory Complexity

• Best Case: O(n) — occurs if the array is already sorted (optimized implementation stops early).
• Average Case: O(n²).
• Worst Case: O(n²).
• Memory Usage: O(1) — in-place sorting, only a few extra variables.

Easy Problems

Problem 1: Sort an Array of Integers

Given an array of integers, sort it in non-decreasing order using Bubble Sort.

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> data = {5, 2, 8, 3, 1};
    bubbleSort(data);
    for (int x : data) cout << x << " ";
    return 0;
}

Problem 2: Sort Characters in a String

Given a string, sort its characters in ascending order.

#include <iostream>
#include <string>
using namespace std;

void bubbleSortString(string& s) {
    int n = s.length();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (s[j] > s[j + 1]) {
                swap(s[j], s[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    string str = "bubble";
    bubbleSortString(str);
    cout << str;
    return 0;
}

Intermediate Problems

Problem 3: Sort a Nearly Sorted Array

An array where each element is at most k positions away from its target position. Use Bubble Sort to fix local inversions efficiently for small k.

#include <iostream>
#include <vector>
using namespace std;

void bubbleSortNearlySorted(vector<int>& arr, int k) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1 && j < i + k; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> data = {3, 1, 2, 6, 4, 5}; // k=2
    bubbleSortNearlySorted(data, 2);
    for (int x : data) cout << x << " ";
    return 0;
}

Problem 4: Detect if Array Can Be Sorted with One Swap

Determine if the array can be sorted by performing at most one swap. Use one pass of Bubble Sort to count out-of-order pairs.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canSortWithOneSwap(vector<int>& arr) {
    int n = arr.size();
    vector<pair<int,int>> bad;
    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) bad.emplace_back(i, i + 1);
        if (bad.size() > 1) return false;
    }
    if (bad.empty()) return true;
    int i = bad[0].first, j = bad[0].second;
    swap(arr[i], arr[j]);
    return is_sorted(arr.begin(), arr.end());
}

int main() {
    vector<int> data = {1, 3, 2, 4};
    cout << (canSortWithOneSwap(data) ? "Yes" : "No");
    return 0;
}

Hard Problem

Problem 5: Count Number of Swaps to Sort an Array

Given an array, count the total number of swaps Bubble Sort would perform to sort it. Useful as a measure of "inversion count."

#include <iostream>
#include <vector>
using namespace std;

long long countBubbleSortSwaps(vector<int>& arr) {
    int n = arr.size();
    long long swapCount = 0;
    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]);
                ++swapCount;
            }
        }
    }
    return swapCount;
}

int main() {
    vector<int> data = {5, 1, 4, 2, 8};
    cout << "Total swaps: " << countBubbleSortSwaps(data);
    return 0;
}