Bubble Sort

Code

C language code:

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int 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]);
    
    bubble_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Code Explanation

1. Initialization: The array arr is the array to be sorted, and n is the length of the array.
2. Main sorting loop:
   • The outer for loop controls the number of passes, from pass 0 to pass n-2. (The last element is automatically sorted.)
   • The inner for loop controls the number of comparisons per pass, from element 0 to element n-i-2.
   • Compares adjacent elements; if the preceding element is greater than the following element, the two are swapped.
3. Result output: After sorting is complete, the sorted array is printed.

Example Run

Assuming the input array is {64, 34, 25, 12, 22, 11, 90}:

1. Initial state: {64, 34, 25, 12, 22, 11, 90}
2. First outer loop (i=0):
   • Compare and swap: {34, 64, 25, 12, 22, 11, 90}
   • Compare and swap: {34, 25, 64, 12, 22, 11, 90}
   • Compare and swap: {34, 25, 12, 64, 22, 11, 90}
   • Compare and swap: {34, 25, 12, 22, 64, 11, 90}
   • Compare and swap: {34, 25, 12, 22, 11, 64, 90}
   • Last pass: {34, 25, 12, 22, 11, 64, 90}
3. Second outer loop (i=1):
   • Compare and swap: {25, 34, 12, 22, 11, 64, 90}
   • Compare and swap: {25, 12, 34, 22, 11, 64, 90}
   • Compare and swap: {25, 12, 22, 34, 11, 64, 90}
   • Compare and swap: {25, 12, 22, 11, 34, 64, 90}
   • Last pass: {25, 12, 22, 11, 34, 64, 90}
4. This repeats until the array is fully sorted.

Final result: {11, 12, 22, 25, 34, 64, 90}

Time Complexity Analysis

The time complexity of bubble sort depends on the initial order of the array.

• Best-case time complexity: When the input array is already sorted, only $O(n)$ comparisons are needed with no swaps, giving a time complexity of $O(n)$.
• Worst-case time complexity: When the input array is in reverse order, bubble sort requires the maximum number of comparisons and swaps, giving a time complexity of $O(n^2)$.
• Average time complexity: In general cases, the time complexity of bubble sort is $O(n^2)$.

Space Complexity Analysis

Bubble sort is an in-place sorting algorithm that requires no additional auxiliary space, so the space complexity is $O(1)$. In this implementation, we only use a few extra variables (i, j, temp), so the space complexity remains at a constant level.

Advantages and Disadvantages

Advantages:

• Simple and easy to implement.
• Stable sorting algorithm; does not change the relative order of equal elements.
• In-place sorting; low space complexity.

Disadvantages:

• High time complexity, especially inefficient for large-scale data.
• Even when the array is partially sorted, complete comparison and swap operations are still required.

Applicable Scenarios

Bubble sort is suitable for the following scenarios:

• Sorting small datasets.
• When a simple and stable sorting algorithm is needed.
• Learning and teaching purposes, to understand basic sorting principles.

Summary

Bubble sort is a simple and intuitive sorting algorithm that works by repeatedly comparing and swapping adjacent elements, causing larger elements to gradually "bubble" to the end of the array. Although its worst-case time complexity is high, in specific scenarios, especially with small datasets, bubble sort remains an effective choice.