Bubble Sort Algorithm

What is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This process is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.

How Bubble Sort Works

Bubble Sort repeatedly compares and swaps adjacent elements if they are in the wrong order. This process continues until no more swaps are needed, indicating that the list is sorted. Here is a step-by-step explanation:

  1. First Pass:
    • Compare the first two elements. If the first element is greater than the second, swap them.
    • Move to the next pair of elements and repeat the comparison and swap process.
    • Continue this process until the end of the list.
  2. Subsequent Passes:
    • Repeat the entire process for the remaining unsorted elements.
    • With each pass, the next largest element moves to its correct position.
  3. Termination:
    • The algorithm stops when a complete pass is made without any swaps, indicating that the list is sorted.

Example of Bubble Sort

plaintext
Let's take an example of sorting the list [5, 1, 4, 2, 8]:
Initial List: [5, 1, 4, 2, 8]

First Pass:
Compare 5 and 1, swap -> [1, 5, 4, 2, 8]
Compare 5 and 4, swap -> [1, 4, 5, 2, 8]
Compare 5 and 2, swap -> [1, 4, 2, 5, 8]
Compare 5 and 8, no swap -> [1, 4, 2, 5, 8]

Second Pass:
Compare 1 and 4, no swap -> [1, 4, 2, 5, 8]
Compare 4 and 2, swap -> [1, 2, 4, 5, 8]
Compare 4 and 5, no swap -> [1, 2, 4, 5, 8]
Compare 5 and 8, no swap -> [1, 2, 4, 5, 8]

Third Pass:
Compare 1 and 2, no swap -> [1, 2, 4, 5, 8]
Compare 2 and 4, no swap -> [1, 2, 4, 5, 8]
Compare 4 and 5, no swap -> [1, 2, 4, 5, 8]
Compare 5 and 8, no swap -> [1, 2, 4, 5, 8]

Since no swaps were made in the third pass, the list is now sorted.

Here are some basic implementations of the Bubble Sort algorithm in C++, Java, and Python.

C++ Program to implement Bubble Sort Algorithm

cpp

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    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;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Java Program to implement Bubble Sort Algorithm

java
public class Main {
    static void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        printArray(arr);
    }
}

Python Program to implement Bubble Sort Algorithm

python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break

def print_array(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()

if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    bubble_sort(arr)
    print("Sorted array: ")
    print_array(arr)

Properties of Bubble Sort

  • Time Complexity:
    • Best Case: O(n) - when the list is already sorted.
    • Average Case: O(n^2) - for random order elements.
    • Worst Case: O(n^2) - when the list is sorted in reverse order.
  • Space Complexity: O(1) - Bubble Sort is an in-place sorting algorithm.
  • Stability: Bubble Sort is a stable sort, meaning it maintains the relative order of equal elements.
  • Adaptability: Bubble Sort can be adaptive if modified to stop early if the list becomes sorted before completing all passes.

When to Use Bubble Sort ?

Bubble Sort is generally not recommended for large datasets due to its O(n^2) time complexity. However, it can be useful for educational purposes and for small datasets where simplicity is more important than efficiency.

Practice Problems on Bubble Sort

  1. Sort an Array of Integers
    • Problem: Given an array of integers, sort the array using Bubble Sort.
    • Example: Input: [64, 25, 12, 22, 11], Output: [11, 12, 22, 25, 64]
  2. Sort an Array of Strings
    • Problem: Given an array of strings, sort the array using Bubble Sort.
    • Example: Input: ["apple", "banana", "cherry", "date"], Output: ["apple", "banana", "cherry", "date"]
  3. Sort an Array in Descending Order
    • Problem: Modify the Bubble Sort algorithm to sort an array in descending order.
    • Example: Input: [64, 25, 12, 22, 11], Output: [64, 25, 22, 12, 11]
  4. Count Swaps in Bubble Sort
    • Problem: Count the number of swaps required to sort an array using Bubble Sort.
    • Example: Input: [64, 25, 12, 22, 11], Output: 10
  5. Optimized Bubble Sort
    • Problem: Implement an optimized version of Bubble Sort that stops early if the array is already sorted.
    • Example: Input: [64, 25, 12, 22, 11], Output: [11, 12, 22, 25, 64]

Frequently Asked Questions (FAQs) on Bubble Sort

Q1: What is the time complexity of Bubble Sort?

  • A: The time complexity of Bubble Sort is O(n^2) in the worst and average cases, and O(n) in the best case when the list is already sorted.

Q2: Is Bubble Sort a stable sorting algorithm?

  • A: Yes, Bubble Sort is a stable sorting algorithm because it does not change the relative order of equal elements.

Q3: What is the space complexity of Bubble Sort?

  • A: The space complexity of Bubble Sort is O(1) because it is an in-place sorting algorithm that does not require additional memory.

Q4: Can Bubble Sort be optimized?

  • A: Yes, Bubble Sort can be optimized by adding a flag to detect if any swaps were made during a pass. If no swaps were made, the list is already sorted, and the algorithm can terminate early.

Q5: When should I use Bubble Sort?

  • A: Bubble Sort is generally not recommended for large datasets due to its O(n^2) time complexity. It can be useful for small datasets, educational purposes, or when the simplicity of the algorithm is more important than efficiency.

Bubble Sort is a simple and easy-to-understand sorting algorithm that works by repeatedly comparing and swapping adjacent elements. While it is not suitable for large datasets due to its O(n^2) time complexity, it provides a good introduction to sorting algorithms and basic algorithmic concepts.

tools

DSA

Related Articles