So now we, we have, we have defined what is a sorting problem.

Again given a list of, of items we want to sort them in for

example, increasing order.

We talked again that it applies to, to,

to lists where we can do order the, we can order the, the elements in them.

So now we're going to, the, the next question will be how do we order things?

Before I do this, I want to remind you of something which is,

probably many of you have done.

Suppose you have an Excel sheet.

So for us, when we grade the, the, you know,

at the end of the semester we have an Excel sheet, or some sheet of grades.

We have multiple columns in this, usually in a,

in a, this, in such as sheet, we have the rows corresponding to students.

If we have 100 students in the class we have 100 rows.

And we have multiple columns, one column is the students name,

one column is the student ID, one column is for the final exam, one column is for

the midterm, seven columns are for seven homework assignments.

Then we have the column for the average and so on.

When, when we want to,

when we want to sort this sheet, to basically assign letter grades.

So we want to say for example all the students that got the grade of,

an average grade between 90 and 100, we're going to give them an A.

So we basically need to sort based on that column that has the average grade.

I don't want to sort alphabetically based on the student name.

Because that doesn't allow me to see where are the categories of grades.

I don't want to sort based on the student ID.

I want to sort based on the average.

Now, notice that when we do this, we don't want to just sort and

shuffle the rows that, that fit only on that column of average.

When I shuffle for example a student has a grade of 9,

of 90 and a student has a grade of 100.

When I shuffle these two rows,

I don't want to just shuffle the 90 and 100, right?

I want to shuffle the entire rows here.

So when the student who got the 90, should be below the student who got 100.

The entire row of that student should be below, right.

So when I shuffle the 100 and 90 I should shuffle the entire rows.

For these two, for these two students, okay.

Because otherwise I'm shuffling the great, and

I have lost all correspondence to the students.

I have sorted grades, but

I have no correspondence between these sort of grades and the actual students.

So when we, when we say we are sorting, if I am sorting based on grades.

Of course it's, it's important to understand that there is

some other data coming with the grade of a student, which we can,

which we referred to sometimes as satellite data, okay.

So the grade that I'm sorting based on, that's the main key based on

which I'm doing the sorting, but attached to that key there is so

much information, so much other data which we call satellite data.

That I also need to, every time I shuffle the keys,

I need to shuffle all the satellite data that is associated with these keys.

So I put, I, I move the grid of 90 to two rows down.

I have to,

to move all the data that's associated with that 90 two rows down, okay.

So I'm not going to be focusing on,

on that satellite data because that's very easy.

It's an implement,

a matter of implementation, of making sure that when you sort based on a key,

you also move all the satellite data that's associated with the keys.

So from now on, we are assuming that we are just fo, focusing on the keys, and

we are sorting ba, based on the keys.

And for

the sake of illustration, I'm going to assume always I'm sorting numbers.

But keep in mind, I can sort strings.

I can sort any list of items that are orderable, that they have total order,

defined on them, okay.

So, how do we do sorting?

How do we do sorting algorithmically?

And of course at this point we have to,

to keep in mind we want to do it in a correct way.

We would like the, the, the, the, the list and to be really sorted correctly.

And second thing we want to do that, efficiently.

Now this is not a problem where probably the first thing that comes to

mind is the brute force manner, so what is the, the, the brute force manner here?

One way of saying it's brute force is remember that the sorting problem is,

in some sense, I can define it as, give me the permutation of the items in

the list that has the specific order, right.

So if I give you a list of, of of numbers, you can loop over all permutations

of that list and find the permutation that satisfies the specific order I want.

But nobody would think about that as a sorting algorithm because you are looping

over all permutation that's n factorial.

If we have n numbers in the list.

That's n factorial, and

even the most naive approach to sorting does much better than that.

And usually sorting, again, even the most naive algorithm that a student can

come up with, is going to take polynomial amount of time.

So we will ignore again that very bad, brute force approach that,

that looks at all permutations.

And let's start thinking first about how you would sort a list of items.

Suppose I give you, I give you a list of,

of a eight numbers for example, 7, 1, 5, 4, 100.

[NOISE] Suppose I have this list of items.

I would like to sort them in increasing order, right.

I want them to be in increasing order.

So one way, so suppose this is the list L, here.

One, one algorithmic approach to solving this is,

let's create another list L prime for example.

We can create list L prime, and

we start building L prime from L in a very simple way.

Since we are, we are sorting in an increasing manner.

We can go through this list, find the smallest item, and copy it here, okay.

So you can go from left to right in this list, start, you know,

you're looking for the minimum.

So initialize the minimum, for example, to infinity.

So I have min, like min here, that I initialize it to infinity.

And as I go through this, I compare the value of min to each value here.

If, if the value is smaller than min, I put that value in min.

So infinity is smaller than 7, then min becomes 7.

1 is smaller than 7, 7 becomes 1.

5 is not smaller, 4 is not smaller, 100 is not smaller, 13 is not,

19 is not, 20 is not.

I am done, I know the min is 1.

So I put 1 here.

Once I have 1 here, I mark it that it is done, right.

I repeat the process.

I initialize min to infinity, and I go through this, and

I will notice that when I go through this, it's going to be replaced by 4.

Infinity's going to be replaced by 4, so I put 4 here.

I am done.

I repeat the process, it will put 5 here.

It repeat the process, it's going to put 7.

I repeat the process, it's going to put 13.

I repeat the process, 19, 20, 100, right.

So this process can be repeated n times, and

at the end I will have this list, right.

This is a simple algorithm.

It is efficient, somehow, because what,

how long does it do take such an algorithm?

Again, I'm not writing the pseudocode here but you get the idea.

Is that you go through the entire list the first time to get the smallest one,

the second time to get the second smallest,

the third time to get the third smallest, and so on.

We are doing since we have to, to copy each element here once.

We are doing n times scan of that list.

So I'm scanning the list first, then I'm scanning it second, I'm scanning it third.

So if I don't like remove these elements or

missed, I just mark them that they have been dealt with.

Every time, I'm scanning the, the entire list.

So n times, n times, n times, n times.

I'm scanning it for n elements.

This algorithm will take O of n squared, okay.

This algorithm will take O of n squared.

The other thing about this algorithm that it's doing,

is that I gave it as input, a list L, it gave me back a list L prime.

This is nice, this is fine, but we in some sense wasted some space, right.

In the sense that, I already have memory used for storing the list L and

I'm now using another part of the memory to store the list L prime that is sorted.

In general, when we do sorting, we would like to do sorting in,

in a mechanism that's called in place,

in place sorting that, I sort this in place without using extra memory.

I can just shuffle the items here, and I get L sorted at the end.

So when we describe an alg, a sorting algorithm that does sorting in place.

That algorithm, for example, when I describe the algorithm, it takes input L.

What it returns is output, nothing.

Because it doesn't return output, it actually just modifies this in place.

Okay.

So usually we're sorting algorithm we like them to sort in place,

without having to copy the list somewhere else and do the sorting.

Okay.

But the more important issue here is that this is an O of n squared algorithm.

Again, suppose I have million records, suppose again I have a,

my computer is dealing with, with information about all the,

the citizens of the US, n is about 300 million, I have a list of,

of a 300 million or so social security numbers.

And I want to sort them.

Now, this algorithm is going to take 300 million squared, okay.

That's a very large number.

Can we do better than this, for sorting, okay.

Can we do better than this, for sorting?

The answer is yes.

And we are going to do now, the sorting in a, in a more efficient way

that will drop this running time from O of n squared to O of n, log n.

[NOISE] Okay, o of n, log n, and this is much better than this,

this is much better than this because we dropped one of the ns her into log which

grows again very slowly with the size of the list which is n.

And would be much more preferred in practice, and this is in

fact most sorting algorithm that are used in practice have this running time.

So we can do the sorting problem in time better then O of n squared,

which will be shown next.

A simple quadratic algorithm

Algorithmic Thinking (Part 2)

与讲师见面