Bubble sort is a simple sorting algorithm that repeatedly compares and swaps adjacent elements to gradually move larger values towards the end of the list.
How bubble sort works
Bubble sort operates by scanning through a list multiple times. During each pass, it compares every pair of adjacent items and swaps them if they are in the wrong order. This process continues until the list is fully sorted.
Each complete pass through the list ensures that at least one item has been placed in its final position, typically the largest remaining unsorted value. This gives the visual impression that larger elements "bubble up" to the top of the list (i.e., towards the rightmost end).
Characteristics of bubble sort
In-place sorting: No additional data structures are required apart from temporary variables for swapping.
Stable sorting: Equal elements retain their relative order after sorting.
Simple logic: Easy to understand and implement.
Practice Questions
FAQ
Bubble sort requires multiple passes because it only guarantees that the largest unsorted element is placed at the end of the list after each pass. Even if the list is nearly sorted, smaller out-of-place elements closer to the start of the list take multiple passes to reach their correct position. Without an early termination condition (like using a swapped flag), bubble sort will always complete n - 1 passes regardless of how sorted the list already is. Even with the optimisation, the algorithm must still make at least one full pass through the list to confirm that no swaps are needed and the list is sorted. This cautious approach ensures correctness but leads to inefficiency when only a few elements are out of place. Each pass only compares and swaps adjacent pairs, so elements move only one position at a time, making the sorting process slower even for nearly sorted data.
Bubble sort handles duplicate values effectively and preserves their original relative positions. This is because it only swaps elements when the first is strictly greater than the second during a comparison. If two adjacent elements are equal, no swap occurs. This behaviour makes bubble sort a stable sorting algorithm, which means that identical elements will remain in the same order relative to each other as they were in the original list. Stability is important in situations where elements have secondary attributes that should not be disturbed by the sorting process—for example, when sorting records by surname but keeping first names in the original order. Even if duplicates are spread across the list, bubble sort will still correctly sort all elements without altering the internal sequence of equal values. This feature makes bubble sort predictable and reliable for sorting data that includes repeated elements or ties in value.
To modify bubble sort to sort a list in descending order, the comparison condition must be reversed. In the standard bubble sort, the algorithm swaps elements when the left item is greater than the right to sort in ascending order. For descending order, you swap elements only when the left item is less than the right. This ensures that larger values "bubble" to the beginning of the list rather than the end. The structure of the algorithm, including the loop bounds and optional swapped flag, remains exactly the same. Only the comparison within the if statement needs to be changed from A[i] > A[i + 1] to A[i] < A[i + 1]. This simple change allows bubble sort to handle reverse sorting without requiring a complete rewrite of the algorithm. The number of comparisons and swaps will remain the same, but the sorted output will now place the largest elements at the start of the list.
Bubble sort is generally not suitable for real-time systems or performance-critical environments. This is because its worst-case and average-case time complexity is O(n²), making it very inefficient as the size of the dataset increases. Even with the early-exit optimisation, bubble sort still performs poorly compared to more efficient algorithms like quicksort or mergesort. Real-time systems often require guaranteed and predictable response times, which bubble sort cannot reliably offer for larger or unsorted inputs. Furthermore, in environments where processing power or energy consumption is constrained—such as embedded systems—bubble sort’s repeated passes and high number of operations make it impractical. While it has a low memory footprint and is easy to implement, its lack of scalability severely limits its use in professional, high-demand applications. In such cases, algorithms with better average and worst-case performance characteristics are strongly preferred to ensure system responsiveness and efficiency.
One clear sign of inefficiency during tracing is a high number of comparisons and swaps, especially when these operations occur repeatedly over multiple passes without significant progress in sorting. If a list requires nearly the maximum number of comparisons—such as n * (n - 1) / 2—it suggests the input is either reversed or heavily unsorted, which is the worst-case scenario for bubble sort. Another indicator is when the same elements are repeatedly involved in swaps, moving one position at a time across several passes. This slow "bubbling" of values highlights the algorithm’s inability to move elements efficiently over long distances. Additionally, if tracing reveals that passes continue even after most of the list appears sorted, and the swapped flag is not used, this shows the algorithm is doing unnecessary work. When performance is being assessed through a trace, patterns of repetitive operations and long sorting duration are key indicators that the algorithm is not suitable for the input size or data structure.
