What is sorting?
In computer science, a sorting algorithm refers to arranging elements of a list in an order. They are sorted numerically (0-9), alphabetically (A-Z) or lexicographically (nuisance, nuke).
Example:
["A", "B", ..., "C"][0, 1, 2, 3, 4, 5, 6, 7, 8, 9]["nuisance", "nuke"]
Importance of sorting algorithms
Sorting algorithms greatly reduce the complexity of a problem. Believe me, the correct algorithm can drastically change the time complexity and space complexity of a code. They directly impact the performance of your program.
Where it's used
Searching for an element in a sorted list
Merging two sorted lists
Finding the minimum or maximum element in a list
Sorting data for presentation
Classification
The sorting algorithms can be classified by:
Computational complexity: In general, good behavior is
O(n log n)orO(n²)and bad behavior isO(n²). Ideally, it should beO(n)but this isn't possible in the average case. The optimal measurement would beO(log n).Best case
Worst case
Average case
Swaps for "in-place" algorithms: The number of swaps that are being made.
Recursion: Some algorithms use recursion, some don't while others have a mix.
Stability: The property that ensures that the relative order of elements with equal keys is preserved after sorting. In other words, if two elements have the same key, they will appear in the same order in the sorted output as they did in the original input.
Why the name "Bubble Sort"?
This algorithm goes over every element, compares it with the adjacent one and swaps it if needed. When you visualize it, it sort of bubbles its way upwards and sorts the list.
This algorithm is beginner-friendly and simple to implement. Due to its simplicity, it's also a slow algorithm compared to others. It makes a whole ton of swaps which decreases the efficiency of the algorithm overall.
Pseudocode
Program
Python implementation of bubble sort.
Steps Explained
Step 1: Initial List [6, 5, 3, 1, 8, 7, 2, 4]
Step 2: First Pass
Comparing 6 and 5: Swap →
[5, 6, 3, 1, 8, 7, 2, 4]Comparing 6 and 3: Swap →
[5, 3, 6, 1, 8, 7, 2, 4]Comparing 6 and 1: Swap →
[5, 3, 1, 6, 8, 7, 2, 4]Comparing 6 and 8: No Swap
Comparing 8 and 7: Swap →
[5, 3, 1, 6, 7, 8, 2, 4]Comparing 8 and 2: Swap →
[5, 3, 1, 6, 7, 2, 8, 4]Comparing 8 and 4: Swap →
[5, 3, 1, 6, 7, 2, 4, 8]Result:
[5, 3, 1, 6, 7, 2, 4, 8]
Step 3: Second Pass
Comparing 5 and 3: Swap →
[3, 5, 1, 6, 7, 2, 4, 8]Comparing 5 and 1: Swap →
[3, 1, 5, 6, 7, 2, 4, 8]Comparing 5 and 6: No Swap
Comparing 7 and 2: Swap →
[3, 1, 5, 6, 2, 7, 4, 8]Comparing 7 and 4: Swap →
[3, 1, 5, 6, 2, 4, 7, 8]Result:
[3, 1, 5, 6, 2, 4, 7, 8]
Step 4: Third Pass
Comparing 3 and 1: Swap →
[1, 3, 5, 6, 2, 4, 7, 8]Comparing 3 and 5: No Swap
Comparing 5 and 6: No Swap
Comparing 6 and 2: Swap →
[1, 3, 5, 2, 6, 4, 7, 8]Result:
[1, 3, 5, 2, 6, 4, 7, 8]
Step 5: Fourth Pass
Comparing 3 and 1: Swap →
[1, 3, 5, 2, 6, 4, 7, 8]Comparing 5 and 2: Swap →
[1, 3, 2, 5, 6, 4, 7, 8]Comparing 5 and 4: Swap →
[1, 3, 2, 4, 6, 5, 7, 8]Comparing 6 and 7: Swap →
[1, 3, 2, 4, 5, 6, 7, 8]Result: [1, 3, 2, 4, 5, 6, 7, 8]
Step 6: Fifth Pass
Comparing 3 and 1: Swap →
[1, 3, 2, 4, 5, 6, 7, 8]Comparing 3 and 2: Swap →
[1, 2, 3, 4, 5, 6, 7, 8]Comparing 4 and 5: No Swap
Comparing 5 and 6: No Swap Result:
[1, 2, 3, 4, 5, 6, 7, 8]
The list is now sorted in ascending order using the bubble sort algorithm.
Statistics & Visualization
Static visualization of Bubble Sort (doesn't make sense to me as well, I know).
Here is Bubble Sort visualized in an animated format.
| Case | Time Complexity | Space Complexity |
| Best Case | O(n) | O(1) |
| Worst Case | O(n²) | O(1) |
| Average Case | O(n²) | O(1) |
So should you use it?
If the input data isn't too big and your project is small scale then you can, otherwise it's recommended to go for other sorting algorithms that provide better time complexity which I'll be writing soon.
Thank you!
... for reading it to the very end & stay tuned to find out more!
Have a great day ahead ✨.