Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

A Bubble sort is a simple sorting algorithm that can be easily understood with a real-life analogy. Think of it like sorting floating bubbles:

Comparing Neighbors: Imagine you have a row of bubbles, each with a number. Bubble sort works by repeatedly going through this row and comparing each bubble with the one next to it. If a bubble is larger than the one next to it (assuming you want to sort from smallest to largest), they swap places.
Bubbles Rise to the Top: Just like larger bubbles rise to the top in water, in each pass through the list, the largest unsorted bubble "floats" up to its correct position. This is done by swapping it with its adjacent bubbles until it reaches its right spot.
Repeated Passes: You keep doing this, making multiple passes through the row of bubbles, each time moving the next largest bubble to its correct position, until no more swaps are needed.
Why Called Bubble Sort: It's called 'bubble' sort because with each pass through the data, the largest element in the list 'bubbles up' to the highest unsorted position, similar to how air bubbles in water naturally rise to the surface.

In summary, bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process continues until the list is sorted, much like bubbles rising to the top until they're all in order.

In the main function, we initialize an array and calculate its size, then call bubbleSort to sort the array and printArray to print the sorted array.

//Bubble Sort Demo

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n);

void printArray(int arr[], int size);

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

//Functions
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // Last i elements are already in place
        for (int j = 0; j < n-i-1; j++) {
            // Swap if the element found is greater than the next element
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

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