Bubble Sort

Example

We have an unsorted array:
[64, 25, 12, 22, 11]

The goal is to sort this array in ascending order using Bubble Sort, which works by repeatedly swapping adjacent elements if they are in the wrong order.

---

Step-by-Step Execution:

Initial Array: [64, 25, 12, 22, 11]

1. Pass 1:
   Compare each pair of adjacent elements and swap if needed.
   Steps:

   • Compare 64 and 25 → Swap → [25, 64, 12, 22, 11]

   • Compare 64 and 12 → Swap → [25, 12, 64, 22, 11]

   • Compare 64 and 22 → Swap → [25, 12, 22, 64, 11]

   • Compare 64 and 11 → Swap → [25, 12, 22, 11, 64]

Array after Pass 1: [25, 12, 22, 11, 64]

2. Pass 2:
   Repeat the process for the remaining unsorted portion ([25, 12, 22, 11]).
   Steps:

   • Compare 25 and 12 → Swap → [12, 25, 22, 11, 64]

   • Compare 25 and 22 → Swap → [12, 22, 25, 11, 64]

   • Compare 25 and 11 → Swap → [12, 22, 11, 25, 64]

Array after Pass 2: [12, 22, 11, 25, 64]

3. Pass 3:
   Process the remaining unsorted portion ([12, 22, 11]).
   Steps:

   • Compare 12 and 22 → No swap → [12, 22, 11, 25, 64]

   • Compare 22 and 11 → Swap → [12, 11, 22, 25, 64]

Array after Pass 3: [12, 11, 22, 25, 64]

4. Pass 4:
   Process the last unsorted pair ([12, 11]).
   Steps:

   • Compare 12 and 11 → Swap → [11, 12, 22, 25, 64]

Array after Pass 4: [11, 12, 22, 25, 64]

Final Sorted Array: [11, 12, 22, 25, 64]

---

Pseudocode for Bubble Sort

function BubbleSort(arr, n):
    for i = 0 to n-1:                 # Outer loop for passes
        swapped = false               # Initialize swapped flag
        for j = 0 to n-i-1:           # Inner loop (compares up to n-i-1)
            if arr[j] > arr[j+1]: 
                swap(arr[j], arr[j+1])
                swapped = true

---

Algorithm for Bubble Sort

1. Input: An array arr of size n.

2. Outer Loop: Repeat n-1 times to ensure all elements are sorted.

   • For each pass, assume the last element is sorted.

3. Inner Loop: Compare adjacent elements in the unsorted portion.

   • If arr[j] > arr[j+1], swap them.

4. Stop when no swaps are needed in a pass, indicating the array is sorted.

5. Output the sorted array.

---

C Code: Function to Perform Bubble Sort

#include <stdio.h>

// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;

    // Outer loop for each pass
    for (i = 0; i < n - 1; i++) {
        swapped = 0; // Flag to check if any swaps occurred

        // Inner loop for comparing adjacent elements
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1; // Set flag to indicate a swap
            }
        }

        // If no swaps occurred in this pass, array is already sorted
        if (swapped == 0) {
            break;
        }
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original Array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted Array: ");
    printArray(arr, n);

    return 0;
}

---

Explanation of the Code

1. Outer Loop:
   Controls the number of passes. After each pass, the largest unsorted element "bubbles up" to its correct position.

2. Inner Loop:
   Compares adjacent elements and swaps them if they are in the wrong order.

3. Swapping Logic:
   Temporary variable temp is used to swap two adjacent elements.

4. Optimization (Flag):
   The swapped flag ensures the algorithm terminates early if no swaps occur during a pass, indicating the array is already sorted.

---

Complexity Analysis of Bubble Sort