Bubble Sort
Performance
Press the 'Play Animation' button.
Sorting Statistics
Swaps:
0
Comparisons:
0
Array Accesses:
0
Delay: 45 ms | Size: 20
⚠️ Note: this animated visualization is a work-in-progress. If you are encountering errors or want to replay the animation, please refresh the page.
If you would like to report a bug or suggest an improvement, please create an issue on GitHub.
Understanding Bubble Sort
Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The algorithm gets its name because smaller elements "bubble" to the top of the list during each pass.
It is a stable sorting algorithm, meaning that the relative order of equal sort items is preserved. It is also an in-place sorting algorithm, meaning that it does not require any additional memory to sort the array.
During the sorting process there are the following operations:
- Swaps: Elements are swapped when they are out of order.
- Comparisons: Elements are compared to determine if a swap is needed.
- Array Accesses: Accessing array elements for reading and writing during swaps and comparisons.
For example, given the array [5, 1, 4, 2, 8], the following steps are taken to
sort the array in ascending order:
- First Pass:
[5, 1, 4, 2, 8]
[1, 5, 4, 2, 8]
[1, 4, 5, 2, 8]
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8] - Second Pass:
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8]
[1, 4, 2, 5, 8]
After the first pass, the largest element is guaranteed to be at the end of the array. After the second pass, the second largest element is guaranteed to be in the second to last position. The algorithm repeats this process until the array is completely sorted.
Complexity Analysis
Bubble Sort has the following complexities:
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best Case | Ω(n) | Ω(1) |
| Average Case | Θ(n²) | Θ(1) |
| Worst Case | O(n²) | O(1) |
Bubble Sort is a stable sorting algorithm, meaning that the relative order of equal sort items is preserved.
Code Implementation
Bubble Sort can be implemented in a variety of languages. Below are some examples of implementations in Python, C++, Go, and Java.
Note: these implementations are for educational purposes only, such as preparing for a technical interview or for learning about sorting algorithms. For production code, please use the built-in sorting functions in your programming language's standard library.
When should Bubble Sort be used?
Bubble Sort is a simple sorting algorithm that is used when the number of elements in the
array is small. It is also used when the array is almost sorted (only a few elements are
misplaced). Bubble Sort is not a practical sorting algorithm when the array is large and
contains a large number of inversions. When we say large, we mean that the array contains
n elements where n is greater than 10,000.
Funnily enough, bubble sort is not used in real-world applications because it is not efficient and does not scale well. However, it is a good algorithm to learn because it is simple to understand and implement.