Video 3-1: §3.0 Sorting introduction

0:00 Intro

0:05 welcome back to com526 efficient algorithms in unit 3 we'll talk about sorting and a little bit about dividing conquer Beyond sorting as well the learning outcomes for for this unit are are to know some basic sorting algorithms just because they're very well known and uh I don't want you to embarrass yourself by not knowing them or at least I want to not be responsible for you not knowing and you should know a little bit of the performance characteristics how they differ when they make sense to use more importantly we'll talk about a lower bound so that will be the first the first case where you see the real user uh the real utility of having abstract mathematical models for our computation name that we can prove impossibility results I always like to compare this to uh a little bit what what physics and Engineering in the mechanical engineering would like to have but don't really have uh we can prove impossibility results something like the uh thermodynamic laws or conservation of energy or something like this so where everyone is is convinced it's not possible to convert energy without some loss so if you say I have a wind turbine that creates electricity there's something lost on the way in terms of of heat and

0:16 Learning Outcomes

1:34 and friction and so on that's something that Engineers also know the difference is in computer science we can find lower bounds that we can also achieve so we have a really small gap between what's known to be not possible and how close can we get to it and I think Engineers usually can only dream of that any combustion engine is still far away from the efficiency that would be the limit of of energy preservation there are so many things before that that stop you from getting better and so in a way that's that's a really unique uh featuring computer science it's engineering on one side but also matching lower bounds for some problems uh that's as unique and quite fascinating and the the real reason why I think mathematical models of computation are are so useful for the Practical applications of programming and algorithms all right that was a long long teaser for this one we'll also then see how you can sometimes circumvent lower bounds by going out of the model another interesting another interesting thing and we'll look at some some practical bits uh the python sorting algorithm um and a little bit on on dynamic programming just very briefly in general

3:02 so a bunch of sections uh we'll we'll start easy today work our way through before we go into any detail I want to motivate a bit why why we study this uh fundamental problem so in a way sorting is about the easiest to explain so you have a list of things and you want to bring them in order that's it's very easy to explain to anyone even if they have never programmed on the other end of the spectrum it's still an open problem in uh in that sense if I give you if I ask you what's the best sorting algorithm in terms of the worst case number of comparisons we still don't know and by and large the the last real progress on this question predates most computers it's from the 1950s and since then only very small uh bits have been have been improved on this and so we still don't have a fully satisfied satisfactory answer for that uh so that's that's kind of intriguing um more practical motivation is that sorting is used as a building block in other things we'll see some some examples it just often happens you've seen it just in the data structure section having an invariant that thinks are in order makes life easier because you can

3:05 Why study sorting?

4:28 rely on more on more properties and uh bringing things in order is sorting I will also use this a bit as a playground but uh that's a weak weak excuse to torture you for so long I think

4:47 well um this is this is moved to unit unit five a lot of three parts first uh some of the the basic bits and I want to formally say what what I mean by sorting um we've seen a race before so not not too much to say about them uh the examples will I think always have numbers but of course sorting is more General all you need really is a total ordering relation so this is mathematically well defined for us it's it's fine to if you just uh use the intuitive meaning you have some way of telling which of two things is smaller

5:07 Rules of the game

5:45 um in in Python the way to write this is just this lesser equal operator note that you can you can override this for custom classes so you can Define your own types you can Define new classes and you can implement this this special function with a double underscore and then if you type in your program the Lesser equal operator for your custom objects it will just call this function so you can you can even implement this ordering relation for new kind of data types that you invent uh Java has a similar means not quite as as elegant in the syntax but achieves the same thing with the comparable interface the goal of course is uh to get the array sorted but what do we mean by this more precisely we want to keep the same elements that we had in the list before they should still be in the list afterwards kind of an obvious fact but if if you don't add that I could just zero out the entire array and say yeah I sorted um no no we want the same elements in the array but so that they're uh ascendingly sorted

6:58 I'm usually careful to put lesser equal it's it's not forbidden to have duplicates or have elements that are equal that compare equal or in the in the syntax of this operator X can be less or equal than y and also Y is less or equal than x so in in that sense X and Y are the same why am I stressing this uh it's not necessarily the case that X and Y are exactly the same thing it could be objects say you're you're you have a list of employees and you sort them by their last name by and large That's Unique but not entirely right there might be several people called I don't know Mueller or was it a Smith uh you know there's names that are a bit more a bit more common depending on the country and then uh you want the people still to be different even though they have the same last name so there's a distinction between comparing equal with this less or equal and being the same thing being the same object

8:10 well well for the experts we'll look at internal sorting but uh that's not not too relevant again my check for you is a question that you're not supposed to know the answer if you haven't seen this before but

8:18 Clicker Question

8:39 uh the the question is almost um almost purposefully ambiguous if you start asking these kinds of questions that's probably the signal for me that you've seen something if you want say what's the complexity of sorting In the comparison model in the worst case

9:59 I see a big blob for big ol fan uh yeah I think this was the I can't show this list of answers with the actual counts now the the other trick is uh but the answer to this question be Theta or Big O or something else

10:34 let me leave it with that I think the guess again is around half of you know know this already maybe a few more um and maybe a few yet more who just don't remember yet uh so same same problem same game as before we're in the territory of uh going through something that many of you have seen but not all