3 ms·

Really, really cool. Would anyone like to explain the outlines for the non-programmers among us?

ojbyrne 18y ago
There's a good question. The basic sort algorithm that most people have seen in real life is "selection sort" - it's the algorithm people use to sort cards in, for example, bridge. Find the highest ranking card, put it in the leftmost position, find the next highest ranking card, put it in the next leftmost position, etc. That would be the "naive" algorithm, and it's the slowest, and the first takeaway is that it doesn't scale - it degrades badly the more things you have to sort (Just imagine having a 100 card hand in some expanded card deck - finding the highest ranking card is a problem that the human mind does reasonably well with, but computers have to look at each of those 100 cards one-by-one to figure out which is the highest ranking). So people have developed interesting algorithms that overcome the limitations of the "naive" algo. One key technique used in a lot of the algorithms is "recursion" - basically divide and conquer. It's used in most of the fast algos - quicksort, mergesort, etc. They all divide the whole data set into smaller data sets (in various ways), sort those smaller data sets (which may involve further subdivisions), and then merge them back together (and that gets more complex with the subdivisions). The closest real life characterization of these kinds of algorithms (back to cards) is that they're sort of like sorting the cards and getting all the odd numbers properly sorted in your left hand and then getting all the even numbers sorted in your right hand, and then "riffling" them together in a way that they the odds and the evens mix perfectly. Another key thing that algorithms deal with is "degenerate" or worst cases. Imagine you are dealt a perfectly sorted card hand, except in reverse order. The "naive" algorithm spends a bunch of time reversing the order (take the rightmost card, put it in the leftmost position, get the next rightmost card, put it second from the left,etc, repeat until done) while better algos provide performance nearly the same as almost fully sorted lists (almost equivalent to - leave it the way it is, and mentally assume the opposite side means higher ranked). And that's it for my regurgitation of school days. Yeah, its weak. Friday night.
- microcentury 18y ago
  Very helpful thanks :-)

There's a good question. The basic sort algorithm that most people have seen in real life is "selection sort" - it's the algorithm people use to sort cards in, for example, bridge. Find the highest ranking card, put it in the leftmost position, find the next highest ranking card, put it in the next leftmost position, etc. That would be the "naive" algorithm, and it's the slowest, and the first takeaway is that it doesn't scale - it degrades badly the more things you have to sort (Just imagine having a 100 card hand in some expanded card deck - finding the highest ranking card is a problem that the human mind does reasonably well with, but computers have to look at each of those 100 cards one-by-one to figure out which is the highest ranking). So people have developed interesting algorithms that overcome the limitations of the "naive" algo. One key technique used in a lot of the algorithms is "recursion" - basically divide and conquer. It's used in most of the fast algos - quicksort, mergesort, etc. They all divide the whole data set into smaller data sets (in various ways), sort those smaller data sets (which may involve further subdivisions), and then merge them back together (and that gets more complex with the subdivisions). The closest real life characterization of these kinds of algorithms (back to cards) is that they're sort of like sorting the cards and getting all the odd numbers properly sorted in your left hand and then getting all the even numbers sorted in your right hand, and then "riffling" them together in a way that they the odds and the evens mix perfectly. Another key thing that algorithms deal with is "degenerate" or worst cases. Imagine you are dealt a perfectly sorted card hand, except in reverse order. The "naive" algorithm spends a bunch of time reversing the order (take the rightmost card, put it in the leftmost position, get the next rightmost card, put it second from the left,etc, repeat until done) while better algos provide performance nearly the same as almost fully sorted lists (almost equivalent to - leave it the way it is, and mentally assume the opposite side means higher ranked). And that's it for my regurgitation of school days. Yeah, its weak. Friday night.

microcentury 18y ago
Very helpful thanks :-)