|
|
| What Sorting Teaches Us (Part I) |
|
|
Submitted by Larry on Fri February 9th, 2007 at 11:24:20 AM EST
|
|
I've got something to admit - when I was first exposed to sorting, I did what every AP-taking high school student would do - memorize the chart of different sorting algorithms and their complexity. It wasn't until years later that I finally understood the various different techniques different sorting algorithms employ. We're all familiar with the algorithms, but what are there to learn from the most basic algorithms?
|
The problem is easy to define in plain English: sorting is process of putting things in a certain order. We like structure in the world, and sorting gives us some sort of structure we can build on - the dictionary is sorted alphabetically, in gym class we get sorted by height, and in our schedulers we often sort by time. It is perhaps the most fundamental process, for which there are many algorithms developed for it.
(For the rest of the article, let's just assume the elements are unique - stable sort will have to wait to get its own explanation!)
Let's begin with the simpliest algorithm you can come up with. No, we're not even at bubble sort yet. This one is probably unlikely, but if I were to come up with the most naive to sort, I still probably wouldn't come up with this one.
Create every possible permutation of the array. Since the sorted array is one of the permutations, all we have to do is go through the list of generated arrays! Simple, isn't it?
But there's this little thing call running time. Who knew there were N! possible permutations? No, I'm not merely excited at N - that's N factorial, the thing that grade school teachers like to use, but never really explained why it's useful, but I think it grows fast. How fast? Let's say we can generate one permutation in 1 microsecond (1 x 10^-6 s):
N
1 - faster than you can blink
2 - faster than you can blink
3 - faster than you can blink
9 - 3/10th of a second
10 - 3 seconds
11 - 33 seconds
12 - 8 minutes
20 - about 77,000 years
But wait! You can do better! What if instead of generating every permutation and then going through the list, we can generate the permutations one at a time, and checking that? We can end the algorithm early!
Great! Shortcutting in a heuristic! If the array is already sorted, we're already done!
And that's when you understand why best-case scenarios aren't particularly helpful in analyzing algorithms.
This shortcut will save us time - in fact, since on average we will get to the sorted array somewhere in the middle, we save half the time! How often can you save half your time on a simple algorithm change? The catch? Half the time isn't quite going to do it when you're talking about 77,000 years.
What if your boss hates you? Or your friend wants to play a cruel prank on you? Even though the average time improves with the short cut, they can always devise a case where the worst-case scenario will happen! How do you improve the worst-case scenario?
Welcome to randomized algorithms! We can change this deterministic algorithm into a randomized algorithm! What does it mean? Instead of generating these permutation one by one formulaically, we can still generate these permutations the same way, but randomly choose which one to check! Why is this important?
Because if your random is truly random (that's also another story for another time) then there is no way someone can give you a case that guarantees you the worst-case scenario. The worst-case scenario might still happen, but they have no control over it, and on average, it will run in half the time, regardless of input!
Part II will come soon... spoiler - Bubble Sort makes an appearance, hope you enjoyed this!
|
|
|
|
Related Links:
What Sorting Teaches Us (Part II)
|
Movie Stars doesn't make enough money
|
Logarithmic image transformation
|
Why I don't look at the market
|
Teenager recites 10,980 digits of pi
|
Cars in the next lane do go faster!
|
I love it!
usa_sports on Sat February 10th, 2007 at 06:05:42 AM EST (#504)
|
|
You'll need to login and activate your account before you can post.
|
 Subscribe
Add IW to your blog
|
