So let me talk about a, a, another, one more algorithm, and, a very,

very common problem we have in computer science is sorting.

There's all kinds of reasons for sorting.

Sometimes we want to put things in alphabetical order,

want to put things in numeric order, or you want to rank things in some other way.

So there's many algorithms for sorting.

Here I'm going to just illustrate one of them.

Let's consider the digits 0 through 9, and suppose they're given to us and

they're not in order, and we want to sort them to put them in order.

They might be, say, attached to something else.

Maybe they're rankings of, of candidates for something and

you want to put them in the right order from, from where 0 will be the minimum.

So one algorithm for doing that says the following.

First, put all the objects in some sort of list data structure

where you can scan through the list from beginning to end.

Now go to the beginning of the list,

compare the first two objects, in this case, 6 and 3.

If they're in the wrong order, simply flip them.

And now move on and see if compare 6 to the next item in the list.

If they're in the right order, okay, we're going to go back to the beginning and now

scan forward until we find two ord, two items that are in the wrong order again.

So we do that.

We get to 8 and 1 and we say oh, wrong order, so we flip those, and

then keep going from there.

We look at 8 and 9.

They're in the right order.

So we'll go back again to the beginning of the list,

scan forward till we get the first pair which is in the wrong order.

There's 6 followed by 1, so we flip those.

We move on and continue this process, always flipping things until we,

till we find obviously the right order.

Moving back to the beginning of the list and

scanning forward until eventually the entire list is sorted.

This algorithm is guaranteed to work.

If you write this down in code, it will always sort your list.

It's not the most efficient algorithm possible, because it actually makes many

passes through the list, and depending on how scrambled the numbers were

in the beginning, it might or might not give you an answer very quickly.

So for, we'll be talking about efficiency in another lecture, but this,

this is a way of introducing idea of efficient algorithms.

So an algorithm is a complete and precise description of how to do something.

But if the amount of data you're dealing with is large,

you also want to think about, how do I do that as fast as possible?

So just because the algorithm completes, and it gives you the correct answer,

doesn't mean it's always the best algorithm to use.

And that bubble sort algorithm, which is what I've just described,

is in fact not the fastest way to sort a list of numbers.

There are better ways to do it.