November 6, 2023
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 is repeated until no swaps are needed, which indicates that the list is sorted. We’ll go into more detail on this below.
How bubble sort works
The algorithm works by comparing each pair of adjacent items and swapping them if they are in the wrong order. This process continues through the array until no swaps are required, indicating that the array is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.
Detailed logic behind bubble sort
In bubble sort, the invariant is that at the end of each pass, the largest element among the unsorted elements is moved to its correct position. This results in elements "bubbling up" like a bubble in water to their rightful place, hence the name. Here's a breakdown of the process:
- Start with the first two elements of the array.
- If the first element is greater than the second, swap them.
- Move to the next pair of elements and repeat the comparison and swap if necessary.
- Continue this process until the end of the array is reached, which places the largest element in its final position.
- Repeat the entire process for the remaining elements, excluding the last sorted elements.
- The algorithm terminates when a pass through the array requires no swaps, meaning the array is sorted.
The bubble sort algorithm in js
Optimizing bubble sort
A small optimization to the standard bubble sort algorithm is to reduce the number of items checked each pass since the last item of the previous pass is already in place:
Adaptive bubble sort
To improve the best-case performance, we can introduce an adaptive change to the bubble sort algorithm by adding a flag that checks whether any swaps were made in the inner loop:
With this improvement, if during a pass no swaps are made, the algorithm concludes that the list must be sorted and stops early, thereby improving efficiency.
Writing clean and concise bubble sort
Bubble sort is not suitable for large datasets as its average and worst-case complexity are both O(n^2), where n is the number of items being sorted. There are more efficient algorithms like quicksort, mergesort, or heapsort for larger datasets.
When to use bubble sort
Bubble sort can be a good choice when simplicity is paramount, or when the list is already mostly sorted, as it has a best-case complexity of O(n) when the list is already sorted.
Example usage of bubble sort
To see bubble sort in action, you can use the following source code to sort an array and then print it out:
Common pitfalls and how to avoid them
- Inefficiency on large lists: Since bubble sort has a quadratic time complexity, it's inefficient for large lists. Use more efficient algorithms for sorting large datasets.
- Misunderstanding the algorithm: Ensure you comprehend the inner and outer loop logic to avoid incorrect implementations.
- Mutating the original array: If you don't want to mutate the original array, you should make a copy of it before sorting.
Visualizing bubble sort
Providing visual representation helps to understand the sorting mechanism of bubble sort. Visual aids like animations or step-by-step illustrations show the process of elements being compared and swapped, emphasizing the "bubbling" effect of the larger elements moving to the top.
Array.prototype.sort() method, which is much more efficient for most cases. While
Array.prototype.sort() is a high-level built-in function that works well with all data types and sorts using an advanced algorithm (like quicksort or mergesort depending on the browser), bubble sort serves an educational purpose in illustrating basic algorithm concepts.
Handling complex data
Bubble sort can sort arrays of non-numeric data by providing a comparison function that defines the sort order:
How to Truncate Date in MySQL