Last year, I was reading a fantastic paper on "Quantum Mechanics for Kindergarden". It was not easy paper.
Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or at least handwave) that the average complexity is $O(n \log n)$, and what the best and the worst cases are, to a kindergarden class? Or at least in primary school?
Asked By : jonaprieto
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1367
Answered By : Kevin
At its core, Quicksort is this:
- Take the first item.
- Move everything less than that first item to the left of it, everything greater to the right (assuming ascending order).
- Recurse on each side.
I think every 4-year-old on the planet could do 1 and 2. The recursion might take a little bit more explanation, but shouldn't be that hard for them.
- Repeat on the left side, ignoring the right for now (but remember where the middle was)
- Keep repeating with the left sides until you get to nothing. Now go back to the last right side you ignored, and repeat the process there.
- Once you run out of right and left sides, you're done.
As for the complexity, worst-case should be fairly easy. Just consider an already-sorted array:
1 2 3 4 2 3 4 3 4 4 Fairly easy to see (and prove) that it's $\frac{1}{2}n^2$.
I'm not familiar with the average-case proof, so I can't really make a suggestion for that. You could say that in an unsorted array of length $l$ the probability of picking the smallest or largest item is $\frac{2}{n}$, so...?
Post a Comment