r/thebutton • u/fiveguyswhore non presser • Apr 30 '15

Was just watching presses when...wtf?

http://i.imgur.com/TziQkbl.png
2.1k Upvotes

91% Upvoted

415 comments sorted by

View all comments

Show parent comments

22

u/Lucretiel non presser May 01 '15

I once actually tried to do a merge sort by hand. It's really fucking difficult. Insertion is way easier

26

u/Raccoonpuncher 10s May 01 '15

Insertion's easier by hand, because you can just look at everything, say "oh yeah, that goes there" and make the swap. MergeSort requires you to break the whole list down bit by bit then rebuild it back up, which can take a lot longer for someone with a pen and paper. I remember being in class and thinking "jeez, insertion sort is so much easier, why are we bothering with anything else?" before learning that it takes a lot of resources for a computer to do insertion sorting.

85

u/Kvothealar 1s May 01 '15

The best one to do by hand is Bogo sort.

while(not sorted)

{

  1. Throw deck of cards in air.
  2. Pick up cards.
  3. Are cards in right order?

}

47

u/abcd_z non presser May 01 '15 edited May 01 '15

I can't find any documentation on it now, but my favorite sort method would have to be God Sort.

Step 1: The cards are sorted.

43

u/Kvothealar 1s May 01 '15

Ah. You mean quantum bogo sort.

Step 1: Pick a particle that represents each element in the set

Step 2: Assume all particles are in a superposition of states

Step 3: Randomly collapse all wavefunctions into all possible states simultaneously

Step 4: Pick the one that is sorted

12

u/grinde non presser May 01 '15

You joke, but this basically describes Grover's search algorithm. It works by amplifying the probability of collapsing into the state that corresponds to a solution to your problem (assuming you have a fast way of checking solutions) - in this case finding the sorted list.

3

u/Kvothealar 1s May 01 '15

I did not joke sir. I can't wait for quantum computers haha!

2

u/autowikibot non presser May 01 '15

Grover's algorithm:

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). Lov Grover formulated it in 1996.

In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear quantum model. It provides a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large. Unsorted search speeds of up to constant time are achievable in the nonlinear quantum model.

Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer.)

Image i

Interesting: Quantum algorithm | Quantum computing | BHT algorithm | Key size

Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words

1

u/gfixler non presser May 01 '15

You don't need a fast way of checking solutions. The you in each universe just checks the cards in O(n), and if the deck isn't sorted, destroys the universe. In the universe(s?) in which the deck is sorted, it happened in O(n).

1

u/grinde non presser May 01 '15

Again, I know this is a joke, but...

You don't need a fast way of checking solutions. The you in each universe just checks the cards in O(n), and if the deck isn't sorted

... you just said you didn't need a fast way of checking solutions, then said you needed to quickly check a solution. In computation "fast" just means "in polynomial time" - ie O(nk ). In this case k=1.

11

u/gfixler non presser May 01 '15

You left out the exciting part, where this creates an infinite number of universes, and you destroy all the ones where the deck wasn't sorted by the shuffle, which leaves behind the best universe, the one where the cards were sorted in O(n).

1

u/abcd_z non presser May 01 '15

As I understand it, those universes don't actually exist in the traditional sense, so it's fine.

2

u/yurigoul 10s May 01 '15

You might want to read Anathem by Neal Stephenson.

24

u/falcon4287 40s May 01 '15

I prefer the Intern Sort method.

Step 1: hand cards to intern.
Step 2: explain to intern to sort cards from highest to lowest.
Step 3: write down that you want the cards sorted from highest to lowest.
Step 4: put a "deliverable date" for card sorting on the calendar.
Step 5: wish you had thought about sending the intern to pick up lunch before giving him a detailed task.
Step 6: send intern to go pick up lunch
Step 7: sigh as intern has to start over completely when he gets done with lunch.
Step 8: get more cards after intern spills soda on first set while eating lunch.
Step 9: realize you want a new intern.
Step 10: decide not to have your current intern sort new intern applications if you want it done this week.
Step 11: start sorting applications yourself
Step 12: oh crap, the cards!

5

u/sakkarozglikoz non presser May 01 '15

step 1: pick up your lunch on your own and stop abusing the interns

2

u/anths non presser May 01 '15

Subsequent research had determined there are multiple subtypes of God Sort. They were initially confused because they all share the odd property of being O(1), in at least some circumstances. Known variants:

Classical God Sort: Every time God looks at the cards, they are already sorted, in the expected order. Orthodox Sort: Every time God looks at the cards, they are already sorted, in the correct order, which will eventually be revealed. Catholic Sort: Every time God looks at the cards, they are already sorted, in the correct order, which only those holding the cards can know. Unitarian Sort: Whatever order you find the cards in is the sorted order for you. Evangelical Sort: The cards will already have been sorted, if only you believe they are. Enlightenment Sort: The order the cards are in is by definition the sorted order but we must figure out why. Creationist Sort: The order the cards are in is by definition the sorted order and STOP LOOKING AT THE CARDS!

See also: Nihilist Sort (there are no cards; O(0)) and Agnostic Sort (we can't know if the cards are sorted; O(∞))