Bubble Sort
EasyBubble Sort is an elementary sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in wrong order. It is named because smaller elements "bubble" to the top of the list.
Time Complexity
O(n²)Space Complexity
O(1)Category
Sorting
Introduction to Bubble Sort
Bubble Sort is one of the simplest sorting algorithms, often used in introductory computer science courses. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
How It Works
The algorithm gets its name from the way the largest elements "bubble" to the end of the list after each pass. In each iteration:
1. Compare the first element with the second
2. If the first is greater, swap them
3. Move to the next pair and repeat
4. After each complete pass, the largest unsorted element is in its final position
Algorithm Complexity
Best and Worst Cases
Advantages
1. Simple to understand and implement
2. Requires no additional memory (in-place sorting)
3. Stable sorting algorithm (maintains relative order of equal elements)
4. Good for educational purposes
Disadvantages
1. Very inefficient for large datasets
2. Time complexity of O(n²) is poor compared to modern algorithms
3. Not adaptive - doesn't perform better on partially sorted data
4. Rarely used in practice due to better alternatives
When to Use
Variations
1. **Optimized Bubble Sort**: Stop if no swaps occur in a pass
2. **Cocktail Shaker Sort**: Bubble sort in both directions
3. **Comb Sort**: Uses gap sequence instead of adjacent comparisons
Key Takeaways
- Compares adjacent elements
- Swaps if in wrong order
- Largest element "bubbles" to end
- Stable sorting algorithm
- In-place sorting
- Not suitable for large datasets
Implementation
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}