SESO16 - Editorial

editorial
, ,
1

Problem Link

Bubble Sort works by repeatedly traversing the array and swapping adjacent elements if they are out of order. The algorithm consists of two nested loops:

  1. Outer Loop: The outer loop runs n-1 times, where n is the number of elements in the array. Each iteration of the outer loop ensures that the largest unsorted element “bubbles up” to its correct position at the end of the array.
  2. Inner Loop: The inner loop compares adjacent elements and swaps them if the current element is greater than the next element. After each pass through the inner loop, the largest element in the unsorted portion of the array moves to its correct position.
  3. Optimization: The inner loop decreases in size with each iteration of the outer loop because the last i elements are already sorted after i passes.

Code Explanation

void bubbleSort(int arr[], int n) {
    // Outer loop for each pass through the array
    for (int i = 0; i < n - 1; i++) {
        // Inner loop to compare and swap adjacent elements
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1] if they are in the wrong order
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

How It Works

  • Initial State: At the beginning, the array is unsorted.
  • First Pass: The largest element in the array “bubbles up” to the last position after the first pass through the array.
  • Subsequent Passes: With each subsequent pass, the next largest unsorted element moves to its correct position. As a result, after i passes, the last i elements of the array are sorted.
  • Termination: The algorithm stops after n-1 passes because, at this point, all elements are in their correct positions.

Complexity Analysis

  • Time Complexity: The time complexity of Bubble Sort in the worst and average cases is O(n^2), where n is the number of elements in the array. This is because the algorithm uses two nested loops, each iterating over the array. In the best case, when the array is already sorted, the time complexity can be reduced to O(n) if an optimization is applied to detect no swaps during a pass, allowing for an early termination.
  • Space Complexity: The space complexity is O(1) because Bubble Sort is an in-place sorting algorithm, meaning it requires only a constant amount of additional space.