Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order; this process is repeated until the list is sorted. With each full pass, the largest unsorted element "bubbles up" to its correct position at the end of the list. Despite its O(n²) worst-case time complexity making it inefficient for large datasets, bubble sort is widely taught due to its simplicity and ease of understanding.
Worked Example
Problem
Sort the array [64, 34, 25, 12, 22] using bubble sort.
Solution
Pass 1: [64,34,25,12,22] → swap 64,34 → [34,64,25,12,22] → swap 64,25 → [34,25,64,12,22] → swap 64,12 → [34,25,12,64,22] → swap 64,22 → [34,25,12,22,64]. Pass 2: swap 34,25 → [25,34,12,22,64] → swap 34,12 → [25,12,34,22,64] → swap 34,22 → [25,12,22,34,64]. Pass 3: swap 25,12 → [12,25,22,34,64] → swap 25,22 → [12,22,25,34,64]. Pass 4: No swaps needed → sorted.
Answer
Sorted array: [12, 22, 25, 34, 64] in 4 passes.
Bubble Sort Complexity and Properties
| Property | Value | Notes |
|---|---|---|
| Best Case Time | O(n) | Already sorted, with early exit |
| Average Case Time | O(n²) | Random order input |
| Worst Case Time | O(n²) | Reverse sorted input |
| Space Complexity | O(1) | In-place, no extra array |
| Stability | Stable | Equal elements maintain relative order |
| Adaptive | Yes (optimised) | Can detect already-sorted input |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
Quick Sort
Quick sort is a highly efficient, in-place divide-and-conquer sorting algorithm that selects a "pivot" element and partitions the array into two sub-arrays — elements less than the pivot and elements greater than the pivot — then recursively sorts each sub-array. It achieves an average time complexity of O(n log n) and is often faster in practice than merge sort due to better cache performance and lower constant factors. Quick sort is widely used in standard library implementations, including the C++ STL and Java's Arrays.sort for primitive types.
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
The term "bubble sort" was coined because smaller or larger elements gradually "bubble" to the top (or bottom) of the list with each pass, much like air bubbles rising through water. The algorithm was first analysed by Iverson in 1962 and later discussed in Knuth's "The Art of Computer Programming".