Bubble Sort

Concept

Bubble Sort is a simple sorting algorithm that 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 no swaps are needed, which indicates that the list is sorted.

It gets its name because smaller elements "bubble" to the top of the list with each pass.

Characteristics

• Time Complexity:
  • Worst-case: O(n²)
  • Average-case: O(n²)
  • Best-case (already sorted): O(n) (with optimization)
• Space Complexity: O(1) (in-place)
• Stability: Stable
• Not efficient for large datasets.

Code Example (C++)

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Function to perform bubble sort
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no two elements were swapped by inner loop, then break
        if (!swapped) {
            break;
        }
    }
}

// Helper function to print the vector
void printVector(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    std::cout << "Unsorted array: ";
    printVector(data);

    bubbleSort(data);

    std::cout << "Sorted array: ";
    printVector(data); // Should print the sorted array

    std::vector<int> data2 = {5, 1, 4, 2, 8};
    std::cout << "Unsorted array 2: ";
    printVector(data2);
    bubbleSort(data2);
    std::cout << "Sorted array 2: ";
    printVector(data2);

    return 0;
}
// To compile and run (e.g., with g++):
// g++ your_file_name.cpp -o bubble_sort_cpp
// ./bubble_sort_cpp

Code Example (Python)

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n - 1):
        # Last i elements are already in place
        swapped = False
        for j in range(0, n - 1 - i):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no two elements were swapped by inner loop, then break
        if not swapped:
            break
    return arr

# Example usage:
if __name__ == "__main__":
    unsorted_array = [64, 34, 25, 12, 22, 11, 90]
    print("Unsorted array:", unsorted_array)
    sorted_array = bubble_sort(list(unsorted_array)) # Pass a copy if you want to keep original
    print("Sorted array:", sorted_array)

    unsorted_array_2 = [5, 1, 4, 2, 8]
    print("Unsorted array 2:", unsorted_array_2)
    sorted_array_2 = bubble_sort(list(unsorted_array_2))
    print("Sorted array 2:", sorted_array_2)

# To run:
# python your_file_name.py

Visualization (Dynamic Input)