Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements and swaps them if they are in the wrong order.
The pass through the list is repeated until the list is sorted.
How it works:
- Compare adjacent elements
- Swap if they are in wrong order
- Repeat for all elements
- Continue until no swaps needed
Use Cases:
- Educational purposes
- Small datasets
- Nearly sorted data
Time & Space Complexity
Best Case
O(n)
Average Case
O(n^2)
Worst Case
O(n^2)
Space Complexity
O(1)
Performance Characteristics:
- Stability: Stable
- In-Place: Yes
- Adaptive: Yes
- Online: No
Edge Cases:
- Already sorted array
- Reverse sorted array
- Array with duplicates
- Single element array
Implementation
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
Pseudocode
procedure bubbleSort(A: list of sortable items)
n = length(A)
for i = 0 to n-1 do
swapped = false
for j = 0 to n-i-2 do
if A[j] > A[j+1] then
swap(A[j], A[j+1])
swapped = true
end if
end for
if not swapped then
break
end if
end for
end procedure
Test Your Knowledge
What is the best-case time complexity of Bubble Sort?
Correct
0
Attempted
0
Accuracy
0%
Validation Lab
Run deterministic correctness checks across sorting, searching, graphs, DP,
strings, geometry, and advanced algorithms.
Idle. Run tests to verify algorithm integrity.
Passed
0
Failed
0
Time
0ms
-
Suite not run yet
No checks executed.