C++ Program to Implement Bubble Sort

1. Introduction

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping 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.

In this blog post, we will learn how to write a C++ program to implement Bubble Sort.

2. Program Overview

1. Ask the user for the size of the array. 

2. Use a loop to get the array elements from the user. 

2. Repeatedly traverse the array and swap adjacent elements if they are in the wrong order.

3. Continue this process until no swaps are made in a complete pass through the array.

4. Display the sorted array.

3. Code Program

#include <iostream>
using namespace std;

// Bubble Sort function to sort an array
void bubbleSort(int arr[], int n) {
    // Outer loop to traverse through the array
    for (int i = 0; i < n-1; i++) {
        // Inner loop for each pass (larger elements will 'bubble up' to the end)
        for (int j = 0; j < n-i-1; j++) {
            // If current element is greater than the next element
            if (arr[j] > arr[j+1]) {
                // Swapping using temporary variable
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    // Declare the array and its size
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int arr[n];

    // Taking input for the array from the user
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Call bubble sort function to sort the array
    bubbleSort(arr, n);

    // Display the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output:

Enter the number of elements: 5
Enter the elements of the array: 5 6 3 2 1
Sorted array: 1 2 3 5 6

4. Step By Step Explanation

1. bubbleSort Function: This function takes an array and its size as arguments. It uses two nested loops: the outer loop runs for n-1 times, and the inner loop runs for n-i-1 times.

2. Swapping: If the current element is greater than the next element, they are swapped. This ensures that after each iteration of the outer loop, the largest element bubbles up to its correct position.

3. Main Function: Take the input array from the user, sort it using bubbleSort, and then print the sorted array.

Bubble sort has a worst-case and average-case time complexity of O(n^2), where n is the number of items being sorted. There are many efficient algorithms than bubble sort like quicksort, mergesort, etc. However, understanding bubble sort is foundational, and it's often introduced early in computer science courses due to its simplicity.