Bubble Sort

#include <iostream>
using namespace std;

void sortArray(int *arr, int n) {

    // Base case - if the size is 0 or 1, the array is already sorted.
    if(n == 0 || n == 1) {
        return;  // No need to sort if the array is empty or has one element.
    }

    // One pass to move the largest element to the end.
    for(int i = 0; i < n - 1; i++) {
        // Compare adjacent elements and swap if they are in the wrong order.
        if(arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i + 1]);  // Swap elements if the left one is larger.
        }
    }

    // Recursive Call - call sortArray on the reduced size (n - 1).
    sortArray(arr, n - 1);
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate the size of the array

    sortArray(arr, size);  // Call sortArray to sort the array

    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";  // Output each element of the sorted array
    }
    cout << endl;

    return 0;
}

Example Walkthrough:

Let’s see how this function sorts the array {5, 3, 8, 4, 2} step by step:

1. First Call: sortArray(arr, 5)

   • Pass 1: {3, 5, 4, 2, 8} (largest 8 is at the end)
   • Recursive call with size 4.

2. Second Call: sortArray(arr, 4)

   • Pass 2: {3, 4, 2, 5, 8} (largest 5 is now at the correct position)
   • Recursive call with size 3.

3. Third Call: sortArray(arr, 3)

   • Pass 3: {3, 2, 4, 5, 8} (largest 4 is now at the correct position)
   • Recursive call with size 2.

4. Fourth Call: sortArray(arr, 2)

   • Pass 4: {2, 3, 4, 5, 8} (largest 3 is now at the correct position)
   • Recursive call with size 1.

5. Fifth Call: sortArray(arr, 1)

   • Base case reached. The function returns.

Final Output:

Sorted array: 2 3 4 5 8