In the next few videos we'll be exploring our a classic computer science problem.

The problem involves sorting a list of objects from smallest to largest.

As you'll soon see, there are many different ways to do this.

In this lecture you're going to learn about the bubble sort algorithm.

To learn about bubble sort, we'll start with an example.

Here is the first list that we'll sort, it has the values seven, three, five and

two. And we're going to follow the bubble sort

algorithm to sort it. We're going to start at index zero, which

I'm going to label with I. And work towards the end of the list,

which I'm going to label with E. We'll start by bubbling the largest item

in the list into the right most position. We do that by comparing the item in index

i, the 7, with the item in index i plus 1 because 7 is greater than 3, we'll swap

these. Now, the 3 is in index 0 and the 7 is at

index 1. The rest of the list is unchanged.

E is the label of the last position. Remove the i to above the index 1 because

we're about to compare the item at index 1 with the item at index 2.

We compare the item at index i with the item at index i plus 1.

7 larger than 5 so those items are swapped as well.

The i is now above the item at index 2, and e again is still over the last item

in the list. The item at index i, the 7, is compared

with the item at i plus 1, the 2. And those items are swapped.

We've now completed one pass of the bubble sort algorithm, and the largest

item on the list, the seven, is in its correct sorted position.

We'll start the second pass of the algorithm.

This time the end is the second last item of the list, the last item is already

sorted. And we still start at the beginning, so

we'll label that with i. We use this line to distinguish the

unsorted part. From the sorted part.

Like before, we compare the item at index i, with the one at i plus 1, and we swap

if necessary. In this case, we don't need to swap the 5

and the 3. Next the 5 is compared with the 2 and

they are swapped. We've reached the end of the second pass,

and the 5 is now moved into its correct sorted position, the second last position

on the list. There's one more pass to do.

The sorted part of the list now has two items in it; i begins at index zero and

this time, the end is at index one, the last item in the unsorted part of the

list. The item at index i is compared with one

at[UNKNOWN] plus one, and the three and two are swapped.

The third pass of the algorithm is complete and the list is now sorted.

Now that we've seen a specific example, we'll draw a few pictures of the state of

the list in general as the algorithm progresses.

At the beginning the entire list is unsorted.

After some number of passes have been completed, part of the list is unsorted

and part is sorted. The unsorted part goes from the index 0

to index end. End of the algorithm.

The index end is at index 0. And all of the items of the list are

sorted. To be precise the item at index zero is

technically unsorted, but we know that it's smaller than the rest because it's

been compared others. Now let's look at the algorithm.

We'll keep track of the index of the last unsorted items list.

Initially, end will refer to the index of the last item in the list, because the

entire list is unsorted. We know that we need to make several

passes through this algorithm. And in our implementation we'll do that

with a while loop. We stop when end is equal to 0.

So we continue as long as it isn't. In each pass, we bubble once through the

unsorted section of the list to move the largest item to index end.

At that point, the sorted section has grown by one.

So, we decrease the index end by one. Starting at index 0 of the sorted

section, we compare the element at index i with the one at index i+1.

If it's larger than it we swap the items. Notice that we're using a new notation.

The list at index i is assigned the item of the list originally at i plus 1, and

the list at i plus 1 is assigned the item originally at index i.

Also notice the four loop header. The unsorted part of the list goes form

index 0 to index end, but the value of I, the largest value of i, is end minus 1.

That's because in the body of the loop, end minus 1 would be compared to the item

one greater than it, the item at the index end.

Finally let's run the doc test. The test case passed, so there's no

output in the shell.