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

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