Quicksort explained to kids

Question

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?

Answer 1

At its core, Quicksort is this:

1. Take the first item.
2. Move everything less than that first item to the left of it, everything greater to the right (assuming ascending order).
3. 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.

1. Repeat on the left side, ignoring the right for now (but remember where the middle was)
2. 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.
3. 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...?

Answer 2

Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2. Make a bunch of X flash cards, number them 1--X, and shuffle it. Then here's the explanation:

OK, we've got this deck of (let's say 20) cards here. We want to put them in order, so 1 is first, then 2, then 3, and so on. Here's a very quick way to do it.

First, let's go through this deck and make two piles out of it. Half of 20 is 10, so anything bigger than 10 goes in this pile on the right, and anything smaller goes in this pile on the left. (Make sure to demonstrate as you go.)

Now, let's do the same thing with the smaller piles. What's half of 10? (Someone says "five!") That's right! So anything bigger than 5 goes in this pile on the right, and anything smaller goes in this pile on the left.

And over here, we've got the group that's bigger than 10. So half of 10 is 5, and what's 10 plus 5? (Someone says "fifteen!") That's right! So anything bigger than 15 goes in this pile on the right, and anything smaller than 15 goes in this pile on the left.

And now the piles are getting small enough that you can easily look at them and put them in order. Look, here we've got 2, 4, 5, 3, 1. So we just switch them around like this, and you can see 1, 2, 3, 4, 5. So let's do the same thing with the other piles, and then we just put the piles in order, and look! They're in order from 1 to 20!

Congratulations. You've just taught a bunch of children the basic principles of an adaptive quicksort algorithm! You can go a bit deeper than that depending on mental maturity, but going much further beyond this point requires some understanding of formal logic.

As for proving its complexity, that's trickier. It's one of the things that requires formal logic, and they'll have to understand the basic principles of big-O notation in the first place. You might want to hold off on that part at first.

Answer 3

How about this?

Computer Science Unplugged - Sorting Algorithms

It doesn't quite cover all your questions, but it's a good start.

More resources on this topic are linked here.

They also made a video available that explains sorting algorithms (quicksort included) here. This video really helps understand the difference between the different sorting algorithms for young kids.

Answer 4

See the graphical loveliness of this little demo.

.