Bubble Sort

Bubble Sort is a simple, comparison-based algorithm for arranging elements in an array in a specific order. This process continues until the array is sorted, making it an intuitive method for sorting arrays.

Key Characteristics:

• Simplicity: Bubble sort is straightforward to understand and implement.
• Inefficiency for Large Lists: Not suitable for large datasets due to its O(n^2) time complexity.
• Stability: Bubble sort is a stable algorithm that maintains the relative order of equal elements.
• Adaptive: Can be optimized to stop early if the list is sorted before completing all passes, making it adaptive to the initial order of elements.

How Bubble Sort Works?

Bubble Sort is a straightforward algorithm that sorts an array by repeatedly comparing and swapping adjacent elements if they are in the wrong order. The steps of the Bubble Sort algorithm are as follows:

1. Start at the Beginning: Begin with the first element in the array.
2. Compare Adjacent Elements: Compare the current element with the next element in the array.
3. Swap if Necessary: If the current element is greater than the next element, swap their positions. This action moves the higher element towards the end of the array.
4. Continue Through the Array: Move to the next pair of adjacent elements and repeat the comparison and swap process.
5. Complete the Pass: Continue this process until the end of the array is reached. This constitutes one complete pass through the array.
6. Repeat the Process: Start again with the first element for the next pass. With each pass, the number of comparisons can be reduced since the end of the array will progressively become sorted.
7. Check for Completion: After each pass, if no swaps have been made, it indicates that the array is now completely sorted. At this point, the algorithm can stop running.

The process is characterized by the larger elements “bubbling” up to the end of the array with each pass, hence the name “Bubble Sort”.

Here is an image that shows the Bubble Sort Algorithm in action:

The above image shows how Bubble Sort works step by step. It starts with the list [5, 2, 8, 3] and compares each pair of numbers. If the first number is bigger, they swap places. After the first round, the biggest number moves to the end. The second round compares and swaps until the next biggest number is in place. By the third round, no swaps are needed because everything is in the right order. The list is sorted as [2, 3, 5, 8].

Pseudocode for Bubble Sort

This pseudocode accurately demonstrates the Bubble Sort Algorithm:

BubbleSort(Array)
  for i from 0 to Array.length - 1
    set swapped to false
    for j from 0 to Array.length - i - 1
      if Array[j] > Array[j + 1]
        swap Array[j] and Array[j + 1]
        set swapped to true
    if not swapped
        break // Array is sorted

Implementation of Bubble Sort

This example implements the Bubble Sort algorithm in Java:

public class BubbleSort {
  public static void main(String[] args) {
    int[] arr = {2, 5, 1, 6, 9, 5};
    bubbleSort(arr);

    System.out.println("Sorted array:");
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }

  public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;

    // Outer loop for each pass
    for (int i = 0; i < n - 1; i++) {
      swapped = false;

      // Inner loop for comparing adjacent elements
      for (int j = 0; j < n - 1 - i; j++) {
        // Swap if elements are in the wrong order
        if (arr[j] > arr[j + 1]) {
          // Swap arr[j] and arr[j+1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;

          swapped = true;
        }
      }

      // If no swaps happened, the array is already sorted
      if (!swapped) break;
    }
  }
}

Copy to clipboard
Copy to clipboard

Here is the output:

Sorted array:
1 2 5 5 6 9

Copy to clipboard
Copy to clipboard

Time Complexity of Bubble Sort

Overall Time Complexity: O(n^2)

• Iterative Comparison: Each pair of adjacent elements is compared, leading to n-1 comparisons in the first pass, n-2 in the second, and so on.
• Best Case Scenario: O(n) when the array is already sorted, as only one pass will be needed.
• Worst and Average Case: O(n^2) due to the nested loops for comparing and swapping elements.

Note: The overall time complexity of Bubble Sort is predominantly influenced by the number of passes through the array and the comparisons within each pass.

Space Complexity of Bubble Sort

Overall Time Complexity: O(1)

Bubble Sort performs with a space complexity of O(1) because it’s an in-place sorting algorithm that needs only a constant amount of extra memory, such as a temporary variable for swapping and loop counters. It does not use any additional data structures, making it memory-efficient despite its slower performance.

Comparison with Other Sorting Algorithms

Frequently Asked Questions

1. What is the main advantage of Bubble Sort?

The primary advantage of Bubble Sort is its simplicity—it is easy to understand and implement, making it useful for teaching basic sorting concepts and algorithms.

2. What is the main disadvantage of Bubble Sort?

The biggest disadvantage of Bubble Sort is its poor performance on large datasets due to its O(n²) time complexity, which makes it inefficient compared to more advanced sorting algorithms.

3. Is Bubble Sort faster than Merge Sort?

No, Bubble Sort is not faster than Merge Sort. Merge Sort consistently performs better with a time complexity of O(n log n), making it significantly more efficient for large lists.