Bubble Sort Algorithm and Program in C

The algorithm works by repeatedly stepping through the array and comparing adjacent pairs of elements.

1. It looks at the first two elements. If the first is larger than the second, it swaps them.
2. It moves to the next pair (2nd and 3rd elements) and does the same.
3. By the time it reaches the end of the array during the first pass, the absolute largest number is guaranteed to be at the very end.
4. It repeats this entire process for the remaining unsorted elements until no more swaps are needed.

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    // Outer loop for the number of passes
    for (i = 0; i < n - 1; i++) {
        // Inner loop for comparing adjacent elements
        // The largest element bubbles up to the end in each pass
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    printf("Sorted array in ascending order: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

While Bubble Sort is very easy to understand and code, it is highly inefficient for large datasets. Because it relies on nested loops (a loop inside a loop) to compare every element, its worst-case time complexity is O(n²). This means sorting 10,000 items could take 100 million operations!