Sorting Algorithms in C++: Bubble Sort, Quick Sort, and Merge Sort

Introduction

Sorting is a fundamental concept in computer science where elements in an array or list are arranged in a particular order (either ascending or descending). Sorting algorithms are essential in numerous applications, from data analysis to searching algorithms. In this tutorial, we will implement and compare three popular sorting algorithms: Bubble Sort, Quick Sort, and Merge Sort in C++. This comparison will provide insights into their efficiency and use cases.

Objective

The objective of this program is to implement and compare three different sorting algorithms:

• Bubble Sort: A simple, but inefficient algorithm with a time complexity of O(n²).
• Quick Sort: A divide-and-conquer algorithm with a time complexity of O(n log n) on average.
• Merge Sort: Another divide-and-conquer algorithm with a time complexity of O(n log n).

We will analyze these algorithms based on their efficiency, speed, and implementation simplicity.

Code Implementation

#include 
#include 
#include 

using namespace std;

// Bubble Sort implementation
void bubbleSort(vector& 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]);
            }
        }
    }
}

// Quick Sort implementation
int partition(vector& 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);
}

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

// Merge Sort implementation
void merge(vector& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge(arr, left, mid);
        merge(arr, mid + 1, right);

        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector L(n1), R(n2);
        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

// Utility function to display array
void printArray(const vector& arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Main function to test sorting algorithms
int main() {
    vector arr1 = {64, 34, 25, 12, 22, 11, 90};
    vector arr2 = arr1;
    vector arr3 = arr1;

    cout << "Original Array: ";
    printArray(arr1);

    // Bubble Sort
    bubbleSort(arr1);
    cout << "Bubble Sorted Array: ";
    printArray(arr1);

    // Quick Sort
    quickSort(arr2, 0, arr2.size() - 1);
    cout << "Quick Sorted Array: ";
    printArray(arr2);

    // Merge Sort
    merge(arr3, 0, arr3.size() - 1);
    cout << "Merge Sorted Array: ";
    printArray(arr3);

    return 0;
}

Explanation of the Program Structure

This C++ program implements three sorting algorithms: Bubble Sort, Quick Sort, and Merge Sort.

Bubble Sort

The Bubble Sort algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the array is sorted.

Quick Sort

The Quick Sort algorithm selects a pivot element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays.

Merge Sort

The Merge Sort algorithm divides the array into two halves, recursively sorts each half, and then merges the sorted halves back together. The merging process ensures that the result is sorted.

Main Function

The main function initializes a sample array and creates three copies of it to demonstrate the effect of each sorting algorithm. It then prints the array before and after applying each sorting algorithm to show the result of sorting.

How to Run the Program

1. 1. Copy the provided C++ code into a file named sorting_algorithms.cpp.
   2. Open your terminal or command prompt and navigate to the directory where the file is located.
   3. Compile the program using a C++ compiler (e.g., g++):

$ g++ sorting_algorithms.cpp -o sorting_algorithms

1. 1. Run the compiled program:

$ ./sorting_algorithms

1. The output will display the original array followed by the array sorted by Bubble Sort, Quick Sort, and Merge Sort respectively.