Bubble Sort vs. Quick Sort: Performance Analysis of Two Classic Algorithms

Introduction

This C++ program implements and compares the performance of Bubble Sort and Quick Sort on a randomly generated array of integers. By timing each sorting algorithm, the program highlights the differences in their time complexities. Bubble Sort is an (O(n^2)) algorithm, which is generally inefficient for large datasets, while Quick Sort, with an average time complexity of (O(n \log n)), is typically faster.

Here's a C++ program that implements both Bubble Sort and Quicksort and compares their time complexities by measuring the time taken to sort a random array of integers.

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

// Function to swap two elements
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Bubble Sort function
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]);
            }
        }
    }
}

// Partition function for Quick Sort
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Quick Sort function
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to generate a random array of integers
void generateRandomArray(vector<int>& arr, int size) {
    srand(time(0));
    for (int i = 0; i < size; i++) {
        arr.push_back(rand() % 1000); // random integers between 0 and 999
    }
}

int main() {
    int size;
    cout << "Enter the size of the array: ";
    cin >> size;

    vector<int> arr;
    generateRandomArray(arr, size);

    // Measure time for Bubble Sort
    vector<int> arr1 = arr; // copy of original array for Bubble Sort
    clock_t start = clock();
    bubbleSort(arr1);
    clock_t end = clock();
    double bubbleSortTime = double(end - start) / CLOCKS_PER_SEC;

    // Measure time for Quick Sort
    vector<int> arr2 = arr; // copy of original array for Quick Sort
    start = clock();
    quickSort(arr2, 0, arr2.size() - 1);
    end = clock();
    double quickSortTime = double(end - start) / CLOCKS_PER_SEC;

    // Display the results
    cout << "Bubble Sort Time: " << bubbleSortTime << " seconds" << endl;
    cout << "Quick Sort Time: " << quickSortTime << " seconds" << endl;

    return 0;
}

Explanation

1. Bubble Sort:

   • Bubble Sort has a time complexity of (O(n^2)), making it inefficient for large datasets due to repeated comparisons and swaps.

2. Quick Sort:

   • Quick Sort has an average time complexity of (O(n \log n)) and performs faster on large datasets due to its efficient divide-and-conquer strategy.

3. Performance Comparison:

   • The program times both algorithms and outputs the duration for each. Quick Sort is expected to outperform Bubble Sort, especially as the array size grows.

Sample Output

For an array of a large size, output might look like:

Enter the size of the array: 1000
Bubble Sort Time: 0.245 seconds
Quick Sort Time: 0.001 seconds

This example demonstrates that Quick Sort is significantly faster than Bubble Sort on large arrays, illustrating the difference in time complexity.

Conclusion

This program clearly demonstrates the time complexity differences between Bubble Sort and Quick Sort. For larger arrays, Quick Sort performs significantly faster due to its (O(n \log n)) average time complexity compared to Bubble Sort’s (O(n^2)). This performance difference highlights the efficiency of Quick Sort, particularly for larger datasets, making it a preferred choice over Bubble Sort in real-world applications.