Bubble Sort (OCR A-Level Computer Science): Revision Notes

Bubble Sort

Overview

Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are in the wrong order. This process continues until the list is sorted. Although inefficient for large datasets, Bubble Sort is useful for understanding basic sorting concepts and small data sets.

How Bubble Sort Works

• Step 1: Compare the first two adjacent elements.
• Step 2: If the first element is greater than the second, swap them.
• Step 3: Move to the next pair of adjacent elements and repeat.
• Step 4: Continue until the end of the list. This completes one pass.
• Step 5: Repeat the process for multiple passes until no swaps are needed, meaning the list is sorted.

Properties of Bubble Sort

• Stable: Maintains the relative order of equal elements.
• In-Place: Requires only a small, constant amount of extra memory.
• Time Complexity:
  • Best Case: O(n) (when the list is already sorted).
  • Worst Case: O(n²) (when the list is sorted in reverse order).
  • Average Case: O(n²).

Pseudocode for Bubble Sort

METHOD BubbleSort(array)
    n ← array.length
    FOR i FROM 0 TO n - 2
        swapped ← FALSE
        FOR j FROM 0 TO n - i - 2
            IF array[j] > array[j + 1]
                SWAP array[j] AND array[j + 1]
                swapped ← TRUE
        ENDFOR
        IF NOT swapped
            BREAK
    ENDFOR

Python Example

def bubble_sort(array):
    n = len(array)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Swap
                swapped = True
        if not swapped:
            break  # If no swaps occurred, the list is sorted
    return array

# Example usage:
data = [5, 3, 8, 4, 2]
sorted_data = bubble_sort(data)
print(sorted_data)  # Output: [2, 3, 4, 5, 8]

Tracing Bubble Sort

Note Summary