0:00

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.

Â 1:26

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.

Â 5:22

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.

Â 6:16

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.

Â 7:01

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.

Â 8:00

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.

Â