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.