Basic Sorts
For all sorting we are going to imagine that you are trapped in a prison at the bottom of the ocean, because that is where you, and your friends belong. But we have some bad news, all of you have escaped and managed to get to a cannon. booooo hissssss
The only way to fire the cannon is to increase the power based on the weight of the person getting in, and powering it up is faster than lowering the power. So, you have to send everyone up in weight order. Everyone is in a line, but it is out of order and they look to you for help. What do you do?
Bubble Sort
If you managed to think quickly, it might only take you half a day to come up with this idea. You are going going to go up to every person. If they weigh less than the person next to them, I will push them up towards the front, until they are where they are supposed to be. Because you are a fool, you have to go through one final time to make sure everyone is in correct order.
This, is bubble sort. Congrats! You wasted most of the day to come up with one of the most inefficient sorting algorithms. I hope you and your ilk are thrown back in prison. The Big O, in fact the BEST CASE, of this is N^2, so bad. Like real bad. Like give up and live in a nature, don’t go near a computer. You are bad. Stop.
It is possible to modify bubble sort so that it stops when it is fully sorted, which means, in the best case it goes to O(N), but it remains a Big O of N^2.
Selection Sort
Let’s say you decide that your other method is no good. Drats, you might actually escape. But, thankfully for the prison guards, your next go to method is this. You go through all of your friends, finding the lowest weight, and placing them at the front. And you continue to do this until everyone is in the right order.
Slightly more efficient, since you don’t have to go through every friend one last time at the end (like bubble sort) and, you are only searching a smaller group of friends. Since the friends at the beginning already belong there, you don’t need to search them again.
The Big O notation of this would still be O(N^2)
Insertion Sort
Abandoning those two ideas as fruitless, you exclaim to your friends ‘I HAVE GOT IT!’ and propose the following. You realize that what made selection sort faster was the fact that larger and larger parts of the line were already sorted. So, you decide to insert each person where they belong in line. You start at the second person, and compare them to the first. Doing this over and over again until everyone is in the right place.
Since the first two are sorted, then the first three, then first four, all you have to do is put everyone in their place.
Your friends would, hopefully, realize that friendship with you
is a waste of time and elect a new sorting leader. Can you guess
the Big O?
It's O(N^2).
Merge Sort
Imagine you had to sort three hundred tickets to a ball, that you weren’t invited to…again. Well, no worries, maybe if you sort this very efficiently, you can go to the ball this year, because everyone will be so impressed.
What you do is, divide half the tickets into two piles each, then divide those piles into halves, and so on, until each pile has one ticket. You then sort the piles of tickets by comparing piles of one against other piles of one. So, you have ticket 205 and ticket 40. Ticket 40 goes first, then ticket 205. You do this for all piles of one until you have half as many piles of two. Now, you do the same problem again for the piles of two. But, all the tickets are already sorted, making it much easier.
So you look at the first ticket in each pile, then compare their values. Put the lowest value in first, then the next greatest value, doing this all the way up until you have sorted all 300 tickets.
So, how long do you think this solution would take?
If you thought Big O of n log n, then you are wrong! It’s a Big o
of n log n, you silly goose. The above implementation I explained
is actually the “worse” merge sort. If you would like to know the
better one, it will have it’s own page which you can look at.
Quick Sort
Looking at the above sort you realize there is a faster way to accomplish the same task. Instead of continually dividing the tickets into smaller and smaller sizes, you will just randomly split the tickets into two piles, with one ticket in the middle. Any tickets higher in value than the middle ticket will go into a pile on the right, and any value smaller will go into a pile on the left.
This, my dear....frie....acquai....reader is called quick sort.
It is widely considered to be one of the fastest sorts...
Quicksort Is better
Fastest sorting alogrithm?
Quick sort is an unstable sort, if you don't know what that means, go back to the terminology section. Quick sort can actually, in Big O terms be as bad as bubble sort. If, for example the item you are sorting is in exact reverse order, then quick sort will take much longer. However, there are simple ways to check for these edge cases and plan accordingly. As such, quick sort is said to be the fastest sorting alogrithm. Even though in Big O terms, it is n lg n (same as merge sort).
Why is quick sort better? It has to do with memory. In merge sort you are breaking things up into smaller and smaller sections, and when you start to combine these sections, you will end up merging data from all over your computers memory. If you remember from caches (if you read it....), you will know that RAM is a faster way to access items in a computers memory than a hard disk. Quick sort allows a computer to deal with more items in RAM and therefore keep a pseudo cache of items to compare, making it faster for your computer.