Sorting: Ep 07b - Quicksort in Real Life


Uploaded by lcc0612 on 02.02.2010

Transcript:
Hello YouTube ans welcome to another episode of sorting algorithms!
As promised, today I will show you how to Quicksort physical media
For the purposes of today's demonstration
I'm going to use a pack of cards - Right here
Yes, the entire deck
For simplicity we will ignore the suits
We will only look at the numerical values of each card
Picture cards will have their logical values
That means A=1, J=11
Q=12 and K=13
Without further ado, let's jump into the sorting
First I'll prove that there are no strings attached
So I will shuffle the deck
Alright here's the deck, more or less pretty well shuffled
The technique to sorting, say, a deck of cards, using Quicksort
is actually pretty simple. You pick a pivot value
I'm going to pick the first card each time. So 8 in this case.
So now I will split the rest of the cards into two sublists
One on both left and right, just like normal quicksort
On the left, the cards will be smaller than or equals to 8
Cards on the right will be larger than 8
Notice that in my other videos I don't tell you what to do when two same values are encountered
It doesn't matter what you do, as long as you do it the same way every time
If I decide that when a same value is encountered it must go to the right
As long as I do it that way all the time it's going to be ok
Similarly to what I'm doing now, whenever two equal cards are encountered
I'll put it to the left. And as long as I do that every time
It's going to be fine
What I will do now is split the cards into two sublists
Alright, what next?
Remember that quicksort keeps moving left until there's nothing left on the left side
And then move on to the right side
So I will now repeat the same process on the left sublist
So now I'll move the existing pivot and right sublist aside. Don't worry I won't mess them up.
So we pick a pivot. "2" in this case since I've made it a rule to use the first card.
We can pick a more optimized pivot knowing that this list is all less than 8
In this case maybe "4"
Because then you get even sublists on each side
But we'll stick to "2", it'll work out anyway
Alright, this is done pretty quickly.
Once again we move to the left sublist
Since this is real-life sorting
And since we know it's all "A"s and "2"s
We do not need to continue quicksorting
So we can take some liberties since we're not discussing the actual computer algorithm
Knowing that it's all "A"s, I will not quicksort further, but instead simply move those into the sorted pile
I'll form a seperate pile offscreen, with all the "A"s in place
Since the "2"s are done as well, we'll stick that onto the sorted pile
Don't worry about the sorted pile being offscreen, there's nothing to see there anyway
Now let's see what we had before
Since we've done up the left sublists, we move to the right sublists
We'll work on this pile now, the twos were on its left before
A quick inspection shows that "7" doesn't make a very good pivot
But it's ok, we'll stick to it
But it's ok, we'll stick to it
But it's ok, we'll stick to it
The process will simply repeat itself, but notice that we have 4 eights lined up
We'll shift that aside first
Remember, quicksort always works on the left sublists
The "7" is already in place, as a pivot, and we will now sort its left sublist
Off we go, pick the pivot, and sort the cards!
We've isolated the "3"s, so we'll add that to the sorted pile
We have "4"s and "5"s. We can also cheat by picking them out.
A stray "5" here was the pivot before. Previously used pivots are always already put in place so we add that to the sorted pile
The next list is all "6"s and "7"s
So let's just cheat
"7" was a pivot before so it's in place
We have a group of "8"s
Well, all sorted
And here's the last pile - The right sublist of the very first quicksort
We'll do something differently this time - I'll pick an optimized pivot instead
This pile contains cards from 9 to K
The most optimized form has the pivot in the center,
And two equally distributed decks on each side
A midpoint pivot can do this, and in this case "J" will do the job
So, we'll go ahead and use "J" as a pivot
The "9"s go to the sorted list
Ony 10s and Js here
We'll seperate the 10s and Js - Doing so is actually a form of selection sort
As usual a pivot from before goes straight to the sorted pile
The last pile has only Ks and Qs, so once again we'll sort it using a selection sort
That's it, here's the whole sorted pile
We'll go through it to see if it's in order
And that's all there is! That's it for this episode of sorting algorithms
Please stay tuned, in the next episode we'll take another complete detour
In the next episode we'll look at the binary tree. Trust me it's relevant
You're watching 0612 TV