Tuesday, December 13, 2011

Quicksort: Like You're 5

One of the problems with the explainations of quicksort that I've noticed is that they often fail to seperate the concept from the implementation. It's easy to get bogged down in the details of iteration, element swapping, etc. without even getting to the meaty center of the discussion: how quicksort works.  So here's my attempt to explain the concept without getting into the implementation.
lets take the set:
[5, 3, 4, 9, 1, 7]
First pick a random element of the set to be the pivot. Let's just pick the first one, 5. So now we have:
Pivot - 5, remaining set [3, 4, 9, 1, 7]
Now iterate through the set and compare them to the pivot. If they are "less than" the pivot, place them in one set, if they are "greater than" the pivot, place them in the other set. We should end up with this:
Less than [3, 4, 1], pivot - 5, greater than [9, 7].
From here we can see that all the elements are in place with respect to the pivot, 5. If we somehow sorted the "less than" and "greater than" sets, we could just merge all the sets together and the whole thing would be sorted. The trick is to sort those "less than" and "greater than" sets, and the way to do that is, of course, using quicksort! Let's sort the "less than" set first. So we have:
[3, 4, 1]
Let's pick the first element to be the pivot again, so we end up with:
pivot - 3, remaining set [4, 1]
repeating the comparison step from before we get:
less than [1], pivot - 3, greater than [4]
Now, we're in the same situation as before only one thing is different; the "less than" and "greater than" sets only have one element, and a one element set is automatically sorted! This is the base case of quicksort: performing quick sort on a one element set (or an empty set) just returns the set. So now all we have to do is merge the three sets together and it's sorted. We end up with:
[1, 3, 4]
Now we go back to where we were before, only now we have the "less than" set already sorted. So we're here:
Less than [1, 3, 4], pivot - 5, greater than [9, 7]
Now we just have to sort that greater than set, once again using quicksort and selecting the first element as the pivot we get:
less than [7], pivot - 9, greater than []
The less than set and greater than set each have 1 or less elements so they're already sorted and we can just merge them together! We get:
[7, 9]
Bringing this sorted set back to where we started we get
less than [1, 3, 4], pivot - 5, greater than [7, 9]
Now the less than and greater than sets are sorted and we can just merge the whole thing together! We get:
[1, 3, 4, 5, 7, 9]
and we're done.

1 comment:

  1. The simplest way to describe quicksort is to explain that every time the elements are compared to the pivot what is actually happening is finding the final position of the pivot. As is the case you are using the pivot always moves into it's final position.

    ReplyDelete