Sorting: Ep 03 - Bubble Sort
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.