Uploaded by lcc0612 on 22.01.2010

Transcript:

Hello YouTube and welcome to the third episode of sorting algorithms

I hope the previous episodes are informative and helpful to you

In particular the first episode which serves as an overview to this entire series

I strongly recommend you watch that episode for a clearer understanding of what I'm on about

In this episode, we'll take a look at the bubble sort

A basic sorting algorithm which works on the principle of conditionally swapping neighboring items.

Let's say we want an ascending ordered list

That means the smaller items go to the left, and the larger items go to the right

Based on this idea, bubble sort compares two neighbouring items

if the item on the right is smaller than the item on the left, they are swapped around

so that now, the left item is smaller

So let's start with the demonstration

Take note that when I select a pair of items, it means the computer is looking at the pair

and checking to see if a swap is required

We start off with 3 and 5 - no swap required as the left item is smaller

Now, 5 and 7 - the same observation is made

7 and 1 - Clearly 7 is larger, so we swap the pair, like so

Once again 7 is larger than 6, so we swap them

7 is larger than 2, so we swap them

Once again 7 is larger than 4, so a swap is done

We'll pause the demonstration for a bit at this point

Do you notice now why they call this the "bubble" sort?

The largest value in the list, "7", moves to the end of the list the same way a bubble rises upwards in a tube

Now we'll continue with the demonstration

Notice the bubbling effect, but also pay attention to the numbers 1 and 2

and take note of the speed in which they move

And that's it - the list is sorted!

Remember the Big O Notation that we covered in Episode 2?

Quickly recapping, the Big O Notation represents the number of items the algorithm needs to process

in terms of "n", which is the number of items in the list.

This is usually expressed as an unknown since the algorithm can handle any number of items

Similarly to the selection sort, the bubble sort takes n² time to complete

because everytime it runs through the list, one item is put in place.

Thus it needs to run through the list of n items, n times to get it all sorted.

Incidentally certain measures can be taken to make bubble sorts slightly more efficient.

Firstly you notice that the items bubbled right to the end are already in place

but the algorithm still wastes valuable processor time comparing those values

A smart implementation of a bubble sorting algorithm

will look at one less item with each pass

choosing to ignore the rightmost values because they're already in place.

Also, as I explained before

a bubble sort algorithm needs to go through a list of n items n times

However, that is actually a worst case scenario.

If a list is already partially sorted

the algorithm can sort the list by going through it less than n times.

Instead of having to look over the sorted list again and again

it can detect that the list has been sorted, and thus will not sort on.

The algorithm can do so by checking to see if any swap has been carried out

in a single pass through the list.

Let's look at the algorithm's last pass through the list again.

The list is, at this point of time, already sorted.

We know that because we can look over the entire list, but the program cannot tell just yet.

Watch the program compare all the neighboring items.

Notice that, since the list is sorted, there is never a point of time where there is a need to swap two items.

Efficient code will notice that, in the entire pass through the list, nothing was swapped around.

Thus, the list is already fully sorted, and there is no need to go through the list any more.

There is one final thing to mention.

In bubble sorts, numbers are sometimes classified as "rabbits" or "turtles".

he reason behind this, is that some items are moved very quickly

and others very slowly.

I told you to notice the large values bubbling quickly towards the end of the list

while smaller values move very little.

In this case, because of their speed, large values are known as rabbits,

while small values are known as turtles.

That's all there is for bubble sort.

In the next episode, I'll show you a similar sorting algorithm

that turns all the values into rabbits!

that turns all the values into rabbits!

Stay Tuned, thanks for watching 0612 TV.

I hope the previous episodes are informative and helpful to you

In particular the first episode which serves as an overview to this entire series

I strongly recommend you watch that episode for a clearer understanding of what I'm on about

In this episode, we'll take a look at the bubble sort

A basic sorting algorithm which works on the principle of conditionally swapping neighboring items.

Let's say we want an ascending ordered list

That means the smaller items go to the left, and the larger items go to the right

Based on this idea, bubble sort compares two neighbouring items

if the item on the right is smaller than the item on the left, they are swapped around

so that now, the left item is smaller

So let's start with the demonstration

Take note that when I select a pair of items, it means the computer is looking at the pair

and checking to see if a swap is required

We start off with 3 and 5 - no swap required as the left item is smaller

Now, 5 and 7 - the same observation is made

7 and 1 - Clearly 7 is larger, so we swap the pair, like so

Once again 7 is larger than 6, so we swap them

7 is larger than 2, so we swap them

Once again 7 is larger than 4, so a swap is done

We'll pause the demonstration for a bit at this point

Do you notice now why they call this the "bubble" sort?

The largest value in the list, "7", moves to the end of the list the same way a bubble rises upwards in a tube

Now we'll continue with the demonstration

Notice the bubbling effect, but also pay attention to the numbers 1 and 2

and take note of the speed in which they move

And that's it - the list is sorted!

Remember the Big O Notation that we covered in Episode 2?

Quickly recapping, the Big O Notation represents the number of items the algorithm needs to process

in terms of "n", which is the number of items in the list.

This is usually expressed as an unknown since the algorithm can handle any number of items

Similarly to the selection sort, the bubble sort takes n² time to complete

because everytime it runs through the list, one item is put in place.

Thus it needs to run through the list of n items, n times to get it all sorted.

Incidentally certain measures can be taken to make bubble sorts slightly more efficient.

Firstly you notice that the items bubbled right to the end are already in place

but the algorithm still wastes valuable processor time comparing those values

A smart implementation of a bubble sorting algorithm

will look at one less item with each pass

choosing to ignore the rightmost values because they're already in place.

Also, as I explained before

a bubble sort algorithm needs to go through a list of n items n times

However, that is actually a worst case scenario.

If a list is already partially sorted

the algorithm can sort the list by going through it less than n times.

Instead of having to look over the sorted list again and again

it can detect that the list has been sorted, and thus will not sort on.

The algorithm can do so by checking to see if any swap has been carried out

in a single pass through the list.

Let's look at the algorithm's last pass through the list again.

The list is, at this point of time, already sorted.

We know that because we can look over the entire list, but the program cannot tell just yet.

Watch the program compare all the neighboring items.

Notice that, since the list is sorted, there is never a point of time where there is a need to swap two items.

Efficient code will notice that, in the entire pass through the list, nothing was swapped around.

Thus, the list is already fully sorted, and there is no need to go through the list any more.

There is one final thing to mention.

In bubble sorts, numbers are sometimes classified as "rabbits" or "turtles".

he reason behind this, is that some items are moved very quickly

and others very slowly.

I told you to notice the large values bubbling quickly towards the end of the list

while smaller values move very little.

In this case, because of their speed, large values are known as rabbits,

while small values are known as turtles.

That's all there is for bubble sort.

In the next episode, I'll show you a similar sorting algorithm

that turns all the values into rabbits!

that turns all the values into rabbits!

Stay Tuned, thanks for watching 0612 TV.