16
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 9
    $\begingroup$ You want to prove the complexity of quicksort... to a bunch of three year olds...? Good luck. $\endgroup$ – DeadMG Apr 19 '12 at 20:25
  • 2
    $\begingroup$ Try to use their language, the problem is that it's very limited and biologically they are not ready for this complexity. Following steps as in an algorithm is not fully developed until they are six or seven years old. You are facing a biological challenge. $\endgroup$ – alfa64 Apr 19 '12 at 20:27
  • 4
    $\begingroup$ I wouldn't actually suggest it for Kindergarten, but search youtube for quicksort (and other sorting algorithms) provide many good representations. I personally prefer the Hugarian folk dance ones. See youtube.com/watch?v=ywWBy6J5gz8 . $\endgroup$ – Muhammad Alkarouri Apr 19 '12 at 20:27
  • 2
    $\begingroup$ The paper you talk about has a catchy title but very complex content such as Hilbert Space Model, so what are you after really? $\endgroup$ – Emmad Kareem Apr 19 '12 at 20:33
  • 2
    $\begingroup$ I would give up on attempting to fully explain quicksort, and instead try to give the kids an understanding of "divide and conquer". Even if they aren't old enough to fully grok recursion, the idea of breaking a big problem into smaller problems would be really valuable. Personally I'd take a solid foundational understanding of divide-and-conquor any day over an incomplete notion of complex algorithms. $\endgroup$ – Vincent Gable Apr 20 '12 at 6:53
14
$\begingroup$

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...?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Maybe (d&c) recursion is best and most naturally explained with the inherent parallelism. $\endgroup$ – Raphael♦ Apr 20 '12 at 8:12
  • 2
    $\begingroup$ I would agree. My instinct was to utilize a metaphor of giving the two piles to your friends to work on. $\endgroup$ – Christian Mann Apr 20 '12 at 8:13
  • 3
    $\begingroup$ I claim that four-year-olds are (with possible exceptions) fundamentally unable to grasp recursion, no matter how hard you try. The brain simply isn’t mature enough. There are well-defined phases in brain development, for instance the point where children become self-aware, where they become aware of future consequences of current actions, and where they first understand sarcasm which follow a tightly controlled schedule which cannot be reordered wilfully and is highly conserved across children. I believe understanding recursion falls in the same category. $\endgroup$ – Konrad Rudolph Apr 20 '12 at 12:35
16
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I do not think your example is not good because you essentially sort on keys, not values, and you can only know what is in position 15 by having sorted already. $\endgroup$ – Thorbjørn Ravn Andersen Apr 19 '12 at 22:43
  • $\begingroup$ @Thorbjørn: Who said anything about key/value pairs? This is a simple integer sort to explain the basic concept. $\endgroup$ – Mason Wheeler Apr 19 '12 at 22:48
  • $\begingroup$ Thinking it over the algorithm you describe is not quicksort, as you do not use a pivot element. $\endgroup$ – Thorbjørn Ravn Andersen Apr 20 '12 at 2:42
  • 1
    $\begingroup$ @ThorbjørnRavnAndersen: Of course he does; it is just that he know which elements are there so can choose the median. $\endgroup$ – Raphael♦ Apr 20 '12 at 8:11
  • $\begingroup$ @Raphael and their distribution. The cards could be any value and color and just have a sticker with their number between 1 and 20. Hence my reference to the key/index and not the value. $\endgroup$ – Thorbjørn Ravn Andersen Apr 20 '12 at 10:29
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ awesome one ! Quite easy to understand. $\endgroup$ – Mayur Patil Sep 24 '18 at 3:28
1
$\begingroup$

See the graphical loveliness of this little demo.

quicksort.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I think that might be too abstract for kids. $\endgroup$ – Raphael♦ Apr 20 '12 at 8:10
  • 3
    $\begingroup$ Not to embarrass myself, but I didn't understand that graphic until I finally was explained quicksort in class. $\endgroup$ – Christian Mann Apr 20 '12 at 8:14
  • $\begingroup$ Have a +1 because this is what first occurred to me when I read the question, but then I'm a visual learner. $\endgroup$ – Joshua Drake Apr 20 '12 at 12:59
  • 3
    $\begingroup$ This is really a wrong way to explain how quicksort works. If you already know quicksort, you can confirm that this animation is about quicksort. If you do not know quicksort, it tells nothing except that quicksort is a fairly fast sorting algorithm which uses some magic. Depending on who the audience are, you may be able to motivate the audience to learn about quicksort by showing this animation, but it does not explain anything important about how it works. $\endgroup$ – Tsuyoshi Ito Apr 20 '12 at 14:17
  • $\begingroup$ The animation is pretty nice but it is so far to be understandable for a beginner even for an undergraduate at first chance. $\endgroup$ – jonaprieto Apr 28 '16 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.