Bubble Sort

Bubble sort works by repeatedly stepping through a list, comparing adjacent elements, and swapping them if they are in the wrong order. The name comes from the way larger elements "bubble up" to their correct position at the end of the list, like bubbles rising in water.

Swapping two elements simply means exchanging their positions in the list. Each complete trip through the list is called a pass. For a list of $n$ elements, bubble sort makes a total of $n-1$ passes to guarantee the list is fully sorted.

In each pass, the algorithm compares every pair of adjacent elements. If you are sorting in ascending order, the largest element after each pass ends up at its correct final position (the end of the list). That element is then excluded from further passes, so the unsorted portion of the list shrinks by one element after every pass.

How it works — step by step

Consider the list numList = [8, 7, 13, 1, -9, 4] (6 elements).

Pass 1: Compare index 0 and 1. 8 > 7 → swap. Now compare index 1 and 2 (the new value at index 1 is 8). 8 < 13 → no change. Compare index 2 and 3: 13 > 1 → swap. Compare index 3 and 4: 13 > -9 → swap. Compare index 4 and 5: 13 > 4 → swap. After pass 1, the largest element (13) is at the last position (index 5). The list now looks like: [7, 8, 1, -9, 4, 13].

Pass 2: Compare index 0 and 1: 7 < 8 → no change. Index 1 and 2: 8 > 1 → swap. Index 2 and 3: 8 > -9 → swap. Index 3 and 4: 8 > 4 → swap. Index 4 and 5 is not compared because index 5 already holds the sorted largest element. After pass 2, the next largest (8) is at index 4. List: [7, 1, -9, 4, 8, 13].

Pass 3: Compare index 0 and 1: 7 > 1 → swap. Index 1 and 2: 7 > -9 → swap. Index 2 and 3: 7 > 4 → swap. Index 3 and 4 is skipped (8 is already sorted). After pass 3, 7 is at index 3. List: [1, -9, 4, 7, 8, 13].

Pass 4: Compare index 0 and 1: 1 > -9 → swap. Index 1 and 2: 1 < 4 → no change. Index 2 and 3 is skipped. After pass 4, 4 is at index 2. List: [-9, 1, 4, 7, 8, 13].

Pass 5: Compare index 0 and 1: -9 < 1 → no change. Index 1 and 2 is skipped. No swaps happen in this pass. The list is already sorted, but the algorithm as written still makes this redundant pass.

Algorithm 5.1: Bubble Sort

BUBBLESORT(numList, n)
Step 1: SET i = 0
Step 2: WHILE i < n REPEAT STEPS 3 to 8
Step 3:   SET j = 0
Step 4:   WHILE j < n - i - 1 REPEAT STEPS 5 to 7
Step 5:     IF numList[j] > numList[j+1] THEN
Step 6:       swap(numList[j], numList[j+1])
Step 7:     SET j = j + 1
Step 8:   SET i = i + 1

Notice the inner loop runs only up to n - i - 1 because the last i elements are already in their correct positions.

Program 5-1: Implementation of bubble sort using Python.

def bubble_Sort(list1):
    n = len(list1)
    for i in range(n):                     # number of passes
        for j in range(0, n - i - 1):      # last i elements are already sorted
            if list1[j] > list1[j + 1]:
                # swap the elements
                list1[j], list1[j + 1] = list1[j + 1], list1[j]

numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
print("The sorted list is :")
for i in range(len(numList)):
    print(numList[i], end=" ")

Output: The sorted list is : -9 1 4 7 8 13

An important improvement

Notice that in the example, the list became sorted after the 4th pass, but the algorithm still performed a 5th pass that did nothing. If no swaps occur during any pass, the list is already sorted and further passes are unnecessary. You can modify the algorithm to stop early by checking whether any swap happened in a pass — if none did, break out of the loop. …