(This might seem like a simple topic that is unimportant (most of us probably just use .sort()) but relearning and diving into the nitty-gritty in university was some food for thought and I decided to share that meal.)
On one corner a master of the shuffle, a fighter who keeps things simple but gets the job done, BUBBLE SORT! On the other corner a fighter who is often compared to the Recursives, if he smells weakness he will end it quickly, hailing from stable town here's INSERTION SORT! And on the other(other) corner a fighter who likes to take his time and throw the same punches no matter who he faces, with an battle tested formula and a simple plan here is SELECTION SORT! Let the battle (that one of my lecturers asked for) begin! DING! DING! DING!
This post will mainly deal with when to use what and how they compare against each other. There will be a quick refresher on how they work but if you want implementation details you'll have to look somewhere else.
Quick Refresher
Bubble Sort
The easiest to remember in my opinion, compare values next to each other, if they are not in order, swap, repeat until sorted.
Insertion Sort
In this algorithm there is a sorted sub-array(or section) and an unsorted one, elements of the unsorted sub-array are inserted into their proper place in the sorted side one by one (by comparing from highest to lowest in the sorted sub-array).
Selection Sort
In selection sort you find the lowest value and swap it with the value in the first spot, find the second-lowest and swap it with the value in the second spot, third-lowest to third spot so on until the last element.
The Head to Head
Stability
A sorting algorithm is stable if equal values do not lose their original order when sorted. Illustrated for clarity in the diagram below:
Both Bubble Sort and Insertion Sort are stable, but Selection is not. This is because the order might be jumbled when swapping, as such:
Whether or not you need stability depends on your use-case.
Complexity - The Main Event
This is where the winners and losers are decided. If stability is not a constraint who do you hedge your bets on? There are 2 main measures that determine which is the most (theoretically?) efficient algorithm, comparison and writing complexity.
Comparisons
All the contending algorithms have a worst and average-case comparison complexity of O(n2). Bubble and Insertion Sort has a best-case comparison complexity of O(n) while Selection Sort's best-case is the same as it's worst case at O(n2).
Why is this? If the elements are already or nearly sorted Bubble Sort and Insertion Sort will require less comparisons (Might be helpful to dry run the algorithms with sorted or nearly sorted arrays). This is not the case for Selection Sort where the algorithm doesn't(or can't) care whether elements are already in order, and will treat all elements as unordered.
Writes
Selection sort has a best, average and worst case complexity of O(n) for writes(or swaps), again this is because the algorithm doesn't(or can't) care if elements are in their proper place already. Insertion and Bubble sort have a best case complexity of O(1), average case of O(n2) and a worst case of O(n2) but due to the nature of the algorithm, bubble sort needs around twice the amount of writes as insertion sort in practice (multipliers are not counted in complexity).
Summary (worst case, average case, best case)
Comparisons
Bubble Sort: O(n2), O(n2), O(n)
Selection Sort: O(n2), O(n2), O(n2),
Insertion Sort: O(n2), O(n2), O(n)
Writes
Bubble Sort: O(n2), O(n2), O(1)
Selection Sort: O(n), O(n), O(n)
Insertion Sort: O(n2), O(n2), O(1)
Where to use what
Insertion sort is to be used in most places because it is likely the list will be partially sorted and depending on the situation stability might be required.
But you can use Selection sort if you want to reduce the amount of writes and you don't need the algorithm to be stable.
But what about Bubble sort?
Is it time for Bubble Sort to retire? :(
It is a very popular sorting algorithm and the first one I learnt in school. This is because it is easy to teach and somewhat more "interesting" that selection sort in my opinion. However people have started to advocate to stop teaching this as Insertion sort works better in nearly all cases. Donald Knuth wrote in The Art of Computer Programming, that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems". Oof. I don't see any disagreement but I did like learning about it even though that might be my nostalgia glasses blurring my mind's eye.
What do you think about bubble sort? Should it be retired, or does it serve a purpose?
Top comments (0)