How Bubble Sort Works: Step-by-Step Explanation

In this article, we’ll explore the bubble sort algorithm in detail, using clear examples to sort a list in ascending order. If you’re new to sorting algorithms, bubble sort is a great place to start because it’s easy to understand and implement. We’ll break down each step of the algorithm so you can see exactly how it works.

Note that, while we focus on sorting in ascending order, the same algorithm can be easily modified to sort in descending order, or even based on custom criteria, by simply changing the way we compare elements.

Brief Introduction

Bubble sort gets its name from the way larger elements “bubble” to the end of the list. The algorithm works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. Here’s how it works:

  1. Bubble sort steps through the list, comparing each element with the one next to it.
  2. If the elements are out of order, it swaps them.
  3. This process is repeated until the list is sorted, often checked by seeing if any swaps occurred during a pass.
  4. With each pass, the largest unsorted element “bubbles” to its correct position at the end of the list.

For more introductory details, check out this article: Introduction to Bubble Sort Algorithm.

Step-by-Step Walkthrough of Bubble Sort Algorithm

Let’s see how bubble sort works by sorting the array [5, 3, 8, 4, 2] in ascending order. We’ll break down each pass and show exactly what happens at each step. A pipe | will be used to indicate the sorted portion of the array so far.

Here’s our starting array: [5, 3, 8, 4, 2]. In each substep, we consider a pair of two adjacent elements and compare them. If the element on the left is greater than the element on the right (left>right) we swap them. This ensures that the larger element moves to the right. If the element on the left is less than or equal to the element on the right, we do nothing and move to the next pair.

First Iteration

  1. Start with the first pair of elements (5, 3):

    • Compare 5 and 3
    • Since 5 > 3, swap them
    • Array becomes: [3, 5, 8, 4, 2]

  2. Move to the next pair (5, 8):

    • Compare 5 and 8
    • Since 5 < 8, no swap needed
    • Array remains: [3, 5, 8, 4, 2]

  3. Next pair (8, 4):

    • Compare 8 and 4
    • Since 8 > 4, swap them
    • Array becomes: [3, 5, 4, 8, 2]

  4. Final pair (8, 2):

    • Compare 8 and 2
    • Since 8 > 2, swap them
    • Array becomes: [3, 5, 4, 2, 8]

After the first iteration, the largest element (8) has “bubbled up” to its correct position at the end: [3, 5, 4, 2 | 8] (Unsorted section of the array is [3, 5, 4, 2] and the sorted section is [8]).

Second Iteration

  1. Start with (3, 5):

    • Compare 3 and 5
    • Since 3 < 5, no swap needed
    • Array remains: [3, 5, 4, 2 | 8]

  2. Next pair (5, 4):

    • Compare 5 and 4
    • Since 5 > 4, swap them
    • Array becomes: [3, 4, 5, 2 | 8]

  3. Next pair (5, 2):

    • Compare 5 and 2
    • Since 5 > 2, swap them
    • Array becomes: [3, 4, 2, 5 | 8]

The second-largest element (5) is now in its correct position: [3, 4, 2 | 5, 8] (Unsorted section of the array is [3, 4, 2] and the sorted section is [5, 8]).

Third Iteration

  1. Start with (3, 4):

    • Compare 3 and 4
    • Since 3 < 4, no swap needed
    • Array remains: [3, 4, 2 | 5, 8]

  2. Next pair (4, 2):

    • Compare 4 and 2
    • Since 4 > 2, swap them
    • Array becomes: [3, 2, 4 | 5, 8]

  3. Check remaining pairs:

    • All elements are in order
    • No more swaps needed

The third-largest element (4) is now in its correct position: [3, 2 | 4, 5, 8] (Unsorted section of the array is [3, 2] and the sorted section is [4, 5, 8]).

Fourth Iteration

  1. Start with (3, 2):

    • Compare 3 and 2
    • Since 3 > 2, swap them
    • Array becomes: [2, 3 | 4, 5, 8]

  2. Check remaining pairs:

    • All elements are in order
    • No more swaps needed

The fourth-largest element (3) is now in its correct position: [2 | 3, 4, 5, 8] (Unsorted section of the array is [2] and the sorted section is [3, 4, 5, 8]).

Finally the array is now fully sorted: [2, 3, 4, 5, 8]

In summary, bubble sort gradually sorts the array by repeatedly comparing and swapping adjacent elements. With each pass, the largest unsorted element “bubbles” to its correct position at the end of the array. Also notice that in each pass/iteration, we do not perform any comparisions on the sorted portion of the list at the end since we know that those elements are already in order.

Key Concepts and Operations

Let’s solidify our understanding of bubble sort by explicitly defining the core concepts and operations involved. Think of these concepts as the fundamental building blocks that make bubble sort work.

Comparison

  • Bubble sort works by comparing two adjacent elements at a time.
  • We check if the element on the left is greater than the element on the right. If it is, it means they are in the wrong order and need to be swapped.
  • This comparison process is carried out for each adjacent pair in the array during each pass.

Swapping

  • When we find two adjacent elements out of order (e.g., [5, 2]), we swap them to put them in the correct order (e.g., [2, 5]).
  • Swapping requires a temporary variable to hold one of the values so we don’t lose it during the swap. Here’s how it works:
temp = a
a = b
b = temp

In this snippet, we store the value of a in temp, then assign b to a, and finally assign the original value of a (stored in temp) to b.

Pass/Iteration

  • Each trip through the array, where we compare and swap adjacent elements, is called a pass or iteration.
  • In each pass, we move from the start of the array to the end of current unsorted portion of the array, making sure the largest unsorted element “bubbles up” to its correct position at the end of the unsorted section.
  • After each pass, you can be sure that the largest element in the unsorted part of the array is in its final, sorted position.

Multiple Passes

  • Bubble sort requires multiple passes through the array. This is because after one pass, only the largest element is guaranteed to be in the correct position.
  • We need to keep making passes until all elements are in the correct order.
  • In the worst-case scenario, the number of passes needed is one less than the number of elements in the array (n - 1 passes for an array of n elements).

Termination

  • How do we know when the array is sorted and we can stop? Bubble sort includes a check to see if any swaps occurred during a pass.
  • If we complete a full pass through the array and no swaps are made, it means all the elements are now in the correct order.
  • For example, if during one of the passes, the array is [2, 3, 4, 5, 8] and no swaps occur, it means every element is less than or equal to the element after it. We can confidently stop the sorting process.

What’s Next?

Now that you understand how bubble sort works step by step, you might want to: