[MUSIC]

In the previous videos, Christine talked about some algorithms for

finding information in large collections of data.

What you saw is,

if the data is organized, then it's easier to do some of these algorithms.

So in this video, we'll talk about ways of organizing data, and

in particular, how to sort it in some order.

And then you'll see some advantages of having it sorted.

So let's think back to binary search, which is one of those algorithms for

searching that Christine presented.

Remember that when we do binary search, at each step of the algorithm

we reduce the number of elements that we need to look at by half.

And so, all in all we look at about log n number of steps if

n is the size of the list of elements that we started.

Okay, so what we remember now is that in order for binary search to work,

the data in our list of elements has to be sorted by what we are searching at.

So for example, if we're looking for.

The country code, the airport code of Essen.

Then what we do with this particular list is we looked about halfway through

our list of elements, and oh, we found it, excellent.

Essen is right in the middle.

All right, so that's kind of silly.

Let's look for another element.

Maybe let's look for Beijing.

Let's look for the airport code of Beijing.

And so, again, we start by looking in the middle of our list of elements.

And then we compare Beijing with Essen and

we see that Beijing is alphabetically earlier than Essen.

And so we only need to look at the first half of the list because we have

the list sorted in alphabetical order.

So the order is really helping us out here.

Now, think about this order.

Sorting, means that we list our element in some order that we decide ahead

of time and is compatible with the search algorithm that we're trying to do,

if the sorting is done as a first step towards searching.

So in particular, for this example,

what we're trying to do is find a city name, and so we're sorting our data.

Based on the first letter and then the second letter of the city, so

we're sorting the city names in alphabetical order.

Now, when you think about airports,

the city is not the only piece of data associated with the airport.

We also have a country that the airport is located in, and so it's conceivable that

instead of sorting by city, we would want to sort our airports by, say, country.

And so we'd want to organize the airports alphabetically according to country.

There's nothing stopping us from doing that, but

we have to think about why we wanna do that.

And so if we're looking for an airport in a given country,

then it would make sense to sort all the airports based on the country name.

And so that's why the sorting has to be compatible with the searching.