Bubble sort is an iterative algorithm that employs a brute-force strategy
to sort a list by repeatedly comparing and swapping adjacent elements that are
in the wrong order. With each pass through the array, the largest unsorted
element "bubbles up" to its correct position at the end. Once the largest
element is in place after the first pass, subsequent passes exclude it,
progressively reducing the unsorted portion by one element each time. Due to
this characteristic, bubble sort can be categorized as a
decrease-and-conquer algorithm, although it is generally not considered
an efficient or strong example of this technique. Passes through the array continue until only a
single unsorted element remains, at which point the entire array is sorted.
To implement bubble sort, the algorithm maintains two pointers: an i
pointer marks the boundary of the unsorted portion and indicates where the next
largest element will settle. Initially, i points to the last element of
the array. Another pointer, j, traverses the array from the beginning to
the position just before i, comparing adjacent pairs of elements
(j and j+1) and swapping them if they are out of order. After the
j pointer passes i-1, the current iteration is complete, and the
largest element from the unsorted portion of the array is now it its proper position i.
The algorithm continues by decrementing i,
resetting j to the start of the array, and beginning the next pass.
Implementation in Java, C++, Python
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void bubbleSort(int arr[], int n) {
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
Time/Space Analysis
To analyze the worst-case complexity of Bubble Sort, we examine how many
comparisons and swaps are performed when the array is initially arranged in
descending order (fully unsorted). This scenario represents Bubble Sort’s worst
case because every possible swap needs to occur to achieve ascending order.
Bubble Sort operates by making multiple passes through the array. On each pass,
it compares adjacent elements, swapping them if they are in the wrong order.
Let's analyze each operation:
First pass: Bubble Sort compares each pair of adjacent elements.
This involves n - 1 comparisons and potentially n - 1 swaps.
After this pass, the largest element is correctly positioned at the end.
Second pass: Now, it must compare each pair up to the second-to-last
element, requiring n - 2 comparisons and potentially n - 2
swaps.
Subsequent passes: Each subsequent pass reduces the number of
comparisons by one, leading to n - 3, n - 4, ..., 1 comparisons
respectively in each pass until the final element is in position.
The total number of comparisons performed is thus the sum of the arithmetic
series:
Since each comparison might lead to a swap, in the worst case the number of swaps
is the same as the number of comparisons.
This leads to an overall worst-case time complexity of O(n²).
Notice that in the best case, even though the number of swaps would be 0 (if the array
is already sorted), the number of comparisons is still n(n - 1)/2 = O(n²).
Although this can be improved (see below),
the average case of Bubble Sort is still O(n²).
This quadratic complexity makes Bubble Sort inefficient for large datasets
compared to more advanced algorithms like quicksort, mergesort, or heapsort,
which have better average-case complexities.
Space Complexity: Bubble Sort operates in-place, only requiring a
constant amount of additional space for i, j, and the temporary
variable used while swapping elements. Thus,
the space complexity is O(1).
Variations/Improvements
Some versions of Bubble Sort bubble the smallest element to the beginning of the array
instead of the largest element to the end. This does not change the time or space
complexity of the algorithm.
The primary optimization for Bubble Sort involves adding an early termination check.
This optimization leverages the fact that if during an entire pass
through the array no swaps are required, the list must already be sorted, and
the algorithm can immediately terminate.
To implement this optimization:
Introduce a boolean variable (often named swapped) initialized
as false at the beginning of each pass.
Set swapped to true whenever a swap is performed.
After each pass, if swapped remains false, the
algorithm terminates early, as it indicates the array is already sorted.
This simple enhancement significantly improves Bubble Sort’s best-case
performance, changing it from O(n²) (in the non-optimized version)
to O(n), as it no longer unnecessarily completes additional passes.
True or False: Bubble sort guarantees a linear time complexity (O(n)) in the worst case.
Multiple Choice: After the first pass of Bubble Sort on an array of size n, which element is guaranteed to be in its correct position?
a) The smallest element
b) The largest element
c) A randomly chosen element
d) The middle element
Fill in the blank: In the optimized Bubble Sort, the algorithm terminates early when __________.
Multiple Choice: Bubble sort is primarily considered an example of what algorithm design strategy?
a) Greedy algorithm
b) Dynamic programming
c) Divide and conquer
d) Brute force
Select all algorithm design strategies below that Bubble Sort could reasonably be classified under (choose all that apply):
a) Greedy algorithm
b) Brute force
c) Decrease-and-conquer
d) Divide-and-conquer
e) Dynamic programming
Short Answer: What is the primary reason Bubble Sort is inefficient for large datasets?
Answer: False
Answer: b) The largest element
Answer: no swaps occur during a complete pass
Answer: d) Brute force
Answer: b) Brute force, c) Decrease-and-conquer
Answer: Its quadratic O(n²) time complexity.
In-Class Activities
Sorting with Cards:
Sort cards with Bubble Sort manually to understand the swaps clearly.
Human Bubble Sort:
Students line up holding cards with numbers. Perform Bubble Sort physically
by comparing adjacent students and swapping positions if needed, clearly
visualizing each step of the sorting process.
Bubble Sort Optimization Discussion:
Divide the class into groups. Each group discusses and proposes one or more
ways to optimize Bubble Sort, then shares their ideas with the class.
Algorithm Comparison:
Provide students with printed arrays of varying sizes and arrangements
(random, nearly sorted, reversed). Students manually sort arrays using
Bubble Sort, Insertion Sort, and Selection Sort to compare and discuss the
performance and efficiency of each method.
Code Tracing Exercise:
Give students short segments of code implementing Bubble Sort. Ask them to
step-by-step trace through sorting small sample arrays, recording each swap
to ensure they understand exactly how the algorithm behaves.
Identify the Sorting Mistake:
Present students with a Bubble Sort implementation that includes an error.
Students work in pairs to identify, explain, and correct the mistake,
reinforcing their understanding of algorithm logic and correctness.
Linked List Bubble Sort
Would it make sense to implement Bubble Sort on a linked list? Explain
the advantages and disadvantages. What would the best and worst case
complexities be?
Problems
Write pseudocode or actual code for Bubble Sort that includes an early
termination check to optimize its best-case complexity. Explain how your
modification improves the algorithm.
Modify Bubble Sort so that it repeatedly moves the smallest unsorted
element to the front of the array (instead of the largest to the end).
Provide your modified code or pseudocode.
Develop a recursive version of Bubble Sort. Clearly outline your algorithm's
base case and recursive steps, and provide pseudocode or actual code for
your solution.
Derive a recurrence relation for the worst-case complexity of your recursive
Bubble Sort from Problem 3. Solve this recurrence to show its complexity is
still O(n²).
Conduct an empirical analysis: Run Bubble Sort on arrays of three types
(sorted, reversed, and randomly ordered) for various array sizes. Record and
analyze the number of comparisons and swaps in each scenario, and summarize
your findings.
Discuss practical scenarios where Bubble Sort might be preferred over faster
sorting algorithms. Consider ease of implementation, small dataset size,
and partially sorted arrays.
Suppose Bubble Sort is run on the array [4, 2, 3, 1, 5]. Show
the state of the array after each pass through the array.
Compare Bubble Sort to Selection Sort. Provide at least two similarities and
two differences between these algorithms, focusing on complexity, algorithm
strategy, and practical performance.
Implement Bubble Sort to sort an array of strings alphabetically. Discuss
any modifications required compared to sorting numerical data.
Cocktail Shaker Sort (also known as Bidirectional Bubble Sort) alternates
between bubbling the largest element up and the smallest element down.
Implement Cocktail Shaker Sort, and discuss any advantages or disadvantages
it has compared to traditional Bubble Sort.