Bubble Sort Algorithm: Pseudocode and Explanation

In the previous article, we explored how the bubble sort algorithm works through a detailed, step-by-step explanation. Now, let’s dive deeper into the algorithmic details by examining the pseudocode for the bubble sort algorithm. By the end of this article, you’ll have a clear understanding of how to implement bubble sort in any programming language. We will use Python-like syntax for our pseudocode, which is easy to read and understand.

Prerequisites:

Understanding the Key Concepts

Before we look at the pseudocode, let’s recap our understanding of the key concepts used in bubble sort:

  1. Comparison:

    • This involves checking if two neighboring elements are in the correct order. “Correct order” depends on whether you’re sorting from smallest to largest (ascending) or largest to smallest (descending).
    • If the elements are out of order, we’ll need to swap them.

  2. Swapping:

    • Swapping is the process of exchanging the positions of two elements.

    • Most of the time, you’ll need a temporary variable to hold one of the values during the swap, so you don’t lose it. For instance, if you’re swapping a and b, you might do:

      temp = a
a = b
b = temp

    • Some languages, like Python, let you swap variables more easily: a, b = b, a.

  3. Pass/Iteration:

    • A pass is a single iteration through the array, where you compare each element with its neighbor and swap them if needed.
    • After each pass, the largest (or smallest, if sorting the other way) unsorted element is guaranteed to be in its final, correct spot at the end of the unsorted part of the array.

  4. Early termination:

    • Bubble sort can be optimized to stop early if no swaps occur during a pass.
    • If no swaps happen in a pass, it means that all adjacent elements in the array are already in the correct order and so we can stop the algorithm.

Algorithm for Bubble Sort

Below are all the steps involved in bubble sort algorithm:

  1. Start at the Beginning: Begin with the first element in the array. This will be the starting point for our comparisons. We will use the first element as a reference point to compare with the adjacent element and decide whether to swap or not.

  2. Compare Adjacent Elements: Compare each element with its next adjacent element in the array. In this step, we are checking two elements at a time to see if they are in the correct order based on whether we are sorting in ascending (smallest to largest) or descending (largest to smallest) order.

  3. Swap if Necessary: If the current element is greater than the next element (for ascending order), swap their positions. This ensures the larger element “bubbles” towards the end of the array. Swapping is crucial to move elements to their correct positions gradually.

  4. Move to the Next Pair: Continue the comparison and swapping process from left to right, moving through the entire array. After comparing and potentially swapping one pair, we shift our focus to the next pair of adjacent elements and repeat the comparison.

  5. Repeat: Repeat steps 1-4 until no swaps are made during a complete pass. This indicates that the array is fully sorted. If we go through the entire array and don’t need to swap any elements, that means all elements are in the correct order, and the sorting is complete.

Pseudocode for Bubble Sort

Here’s the pseudocode for the iterative approach to bubble sort, using Python-like syntax:

def bubble_sort(array):
  # Get the length of the array
  n = len(array)

  # Outer loop: Iterate through the array
  # After each pass, the largest unsorted element "bubbles" to its correct position at the end
  for i in range(n):
    # Initialize a flag to check if any swaps occurred in this pass
    swapped = False

    # Inner loop: Compare adjacent elements and swap them if they are in the wrong order
    # Notice that with each pass, we iterate through one less element
    for j in range(0, n-i-1):
      # Compare adjacent elements
      if array[j] > array[j+1]:
        # Swap array[j] and array[j+1]
        array[j], array[j+1] = array[j+1], array[j]
        # Set the swapped flag to True
        swapped = True

    # If no two elements were swapped in the inner loop, the array is sorted
    if swapped == False:
      break # Exit the outer loop

Explanation of the Pseudocode

  • The outer loop (for i in range(n)) iterates through the array. In the worst-case scenario, the loop runs n times, but it may terminate earlier if no swaps occur in a pass, indicating that the array is already sorted. Each iteration ensures that the largest unsorted element is placed in its correct sorted position at the end of the array.
  • A boolean variable swapped is used as a flag to track whether any swaps occur during a pass (inner loop). If no swaps occur, it means the array is already sorted, and the algorithm can terminate early. This optimization improves the best-case time complexity to O(n) because it avoids unnecessary passes through an already-sorted array.
  • The inner loop (for j in range(0, n-i-1)) compares adjacent elements and swaps them if they are in the wrong order. Notice how with each pass of the outer loop, the inner loop considers one less element because the largest elements are already in their correct positions at the end of the array. This is achieved by n-i-1 in the inner loop.
  • The line array[j], array[j+1] = array[j+1], array[j] is a Pythonic way to swap the positions of two elements in the array without needing a temporary variable. It simultaneously assigns the value of array[j+1] to array[j] and the value of array[j] to array[j+1]. This feature is available in some other programming languages as well.

Example Walkthrough

Let’s walkthrough the bubble sort pseudocode with the array [5, 1, 4, 2, 8].

  1. First Pass (i = 0):

    • swapped = False
    • Compare 5 and 1: Swap, array = [1, 5, 4, 2, 8], swapped = True
    • Compare 5 and 4: Swap, array = [1, 4, 5, 2, 8], swapped = True
    • Compare 5 and 2: Swap, array = [1, 4, 2, 5, 8], swapped = True
    • Compare 5 and 8: No swap, array = [1, 4, 2, 5, 8]
    • swapped is True

  2. Second Pass (i = 1):

    • swapped = False
    • Compare 1 and 4: No swap, array = [1, 4, 2, 5, 8]
    • Compare 4 and 2: Swap, array = [1, 2, 4, 5, 8], swapped = True
    • Compare 4 and 5: No swap, array = [1, 2, 4, 5, 8]
    • Compare 5 and 8: No swap, array = [1, 2, 4, 5, 8]
    • swapped is True

  3. Third Pass (i = 2):

    • swapped = False
    • Compare 1 and 2: No swap, array = [1, 2, 4, 5, 8]
    • Compare 2 and 4: No swap, array = [1, 2, 4, 5, 8]
    • Compare 4 and 5: No swap, array = [1, 2, 4, 5, 8]
    • Compare 5 and 8: No swap, array = [1, 2, 4, 5, 8]
    • swapped is False

  4. Since swapped is False, the algorithm terminates. The array is now sorted: [1, 2, 4, 5, 8].

What’s Next?

Now that you understand the pseudocode, you might want to: