Video 3-0: §3.0 Sorting introduction

0:04 C welcome to unit three of comp 5 to6 efficient algorithms uh we'll look at sorting in detail in this unit and a few other related dividing conquer algorithms much of this first part will be repetition for many of you but then we'll have uh two more um parts that go a little deeper and is also touching on on some of my own research so it's kind of dear to my heart the topic uh but let's get started slowly and before we get started let's have a uh on the record again the the little overview of what sorting algorithms people already know uh bubble sword is really big for some reason bubble sword is always well known even though it's a by all means by by all standards a not great algorithm it's fairy slow but somehow is cute and has a good name I guess good names are important uh the other two big ones are quick sword and merge sword um talk about this uh

1:03 and okay many many other little variants more or less well known Heap Sort is of course another one um that is taking the binary heaps that we use to do sorting if you haven't seen this you can uh you learn a little bit about this in the tutorials and we'll come back to this guy as well radic

1:30 sword there's actually many more it's um sorting is somewhat of a of a standard toy problem that people love to invent new things for um whether or not each and every one of them is is useful is maybe a secondary question this is often something that people do for fun some form of fun I

1:57 guess uh for this module what I would like to uh to take you what I'd like you to take from it is specifically merge sort and quick sort as the two most important and most uh the most important efficient algorithms that are in wide use know what their performance characteristics are then we'll talk briefly about the lower Bound for sorting uh again something many will have seen in undergraduate computer science courses if you've done that um and we'll briefly talk about how you can break that lower bound and then we'll look at uh what happens if you can exploit some existing order in the

2:40 input so there's the uh the overview of the sections uh at the end we'll cover a few other divide and conquer algorithms uh just to show you that many of the concepts that we apply to generate sorting algorithms are more General than that um and the is insightful to have a few examples that are Beyond sorting for that

3:01 uh why still do sorting first of all it's a fundamental problem that still has unsolved Corners uh for example an innocent question could be what's what's an algorithm that uses the fewest number of comparisons to sort n items and kind of tantalizingly this is open we don't really know um at least if you zoom in very closely if you want to know an algorithm exactly uses the minimal number of comparisons that's open and the last substantial progress uh might be from the 50s 1950s uh with a few with a few improvements after that but that's that's kind of the academic motivation of course uh sorting is a sub routine that's used for many other more complicated algorithms or processing steps is a way to remove duplicates from a data said um there's other ways with hashing but sorting might be faster in some some cases uh and many geometric algorithms things like uh uh scanning line algorithms um often use sorting as a pre-processing what we'll focus on here is uh the classic fast sorting methods um in the first part just as a recap how to exploit if the input has some structure to be faster and we'll we'll also talk about parallel algorithms and parallel sorting as one specific topic but not in this unit

4:38 we'll come back later to uh parallel algorithms and then look at sorting again as um one problem where parallel algorithms are interesting because sorting is it's possible to parallelize it to use several cores on a computer to sort but it's not obvious how to do it

5:06 before we start let's um cover a few Basics and uh Define what what we mean when when we say sorting and for uh for most of this uh unit this will be uh the setup um with one exception that I'll comment on when we get to it uh we'll work with arrays of of objects and I'll be generic what objects are it could be anything uh think of some arbitrary python object if you want um I'll I've used this a little bit before but um just to um state that formally again if we have arrays I use this kind of notation with dot dot to indicate that that's a range in the array or that the array has this this size uh python would probably rather have a colon and then the two indices I'm trying to use this notation often where the first index is inclusive and the second is exclusive which is exactly what python would do with a colon but I'll I'll use these parentheses to make that visible in the syntax uh where is it standard if you use square brackets that it's inclusive on both ends so that's just so that you don't misread um the pseudo code that comes uh what we assume as well is that the objects are somehow ordered we

6:26 talked about this for binary search trees and heaps already uh it's the same assumption so there's given two objects from our array there's a way to tell which is smaller now here we'll be happy if this is just a lesser equal operator so you can ask is this lesser equal than this yes or no that's what we'll work with uh python has of course this buildin as lesser equal operator you can override it for custom classes by implementing or overwriting this this function with a double underscore I don't know if uh if you're new to python maybe you don't know this yet uh it's just a way to define the Lesser equal symbol to mean something for your custom objects uh Java has as the second language that many people know uh has a similar um setup so there's a specific interface comparable that you can Implement and then objects have a compare two method uh that behaves essentially if you compare it with zero it behaves like the compar and operators so long story short given two objects I can decide which one is smaller and then the goal is to rearrange them in the array so that they're in sorted order afterwards so unless it's otherwise stated we'll assume we sort in place so we produce

7:46 the sorted list in the same array that we're given as input that doesn't say that some algorithms don't use extra memory to do the Sorting but at the end it should be back where we started

8:01 right for the experts um we'll focus on internal sorting which means methods that are effective if the input is fitting in main memory small enough to be held in one computer and in main memory so that would be a few gigabyte easily on a large server maybe a few hundred gigabytes on a large server maybe a terabyte um if it's much more than that then you probably use different algorithms and that's a separate topic that we won't touch on we also assume for now for this unit that we're just doing everything sequential single

8:41 processor apart from asking you just uh for names of sorting algorithms Let's uh do the slightly more more theoretical version of I will comment a bit more on what this question

10:06 had 111 people vote earlier let's see how close we get to that uh I don't know why this picture showed up I didn't intend the picture to be part there but if you recall that was part of the prior knowledge survey as well and that's where that screenshot is from uh let's leave it with that so you can can see various answers uh yeah if you sent the the letter from before then you'll have to uh look up what that stood

10:57 for not very convenient to do yeah sorry sorry I have to remove that image that's just confusing so the most voted answer was G if um if I hide this again G was order n log Big O of n log n and then various other other things

11:26 so let me unpack the question first uh there's a few things that maybe we haven't spoken about in in full detail yet I'm asking about the complexity of a problem that's a bit of a weird thing to do right we've talked about the cost of running an algorithm uh but this sorting is not an algorithm that's a problem it's an algorithmic task so what do we even mean by complexity here uh what what algorithms people mean in this context is uh give me the the best you know about this problem how fast can you do it and what's the best impossibility result you know about that problem and for some lucky problems and sorting is one of them we have matching upper and lower bounds up to very small error margin so we know precisely how well we can do and we know ways to do that well that's pretty striking it's one of the things that computer science is is fairly unique at uh show me some of the other engineering disciplines where you can where you can have so close uh gaps between what's theoretically possible and what's actually achieved in practice I always bring this example of a combustion and internal combustion engine you know a car motor um we know there's some physical limits like

12:46 preservation of energy or things like that but we're far away in the efficiency of actual machines in actual engines from that limit computer science for sorting and other problems we're right at the limit there's a theoretical lower bound of how fast you can go and we're almost matching it that's pretty cool so that's what people mean when they ask about the complexity of the problem give me the best impossibility result and the best algorithm that you know and hopefully these are close um and uh for sorting well we know that we can do it in N log end time uh and we will come back to that of course um and uh we also know there's a lower bound of nlog n and those those essentially match if you're only looking at the Big O classes so you could say the complexity is fed Del n log

13:45 n and the the what what this statement means there's a lower bound of Omega n log this and those two things together so if you have these two they imply that you can say the problem has this complexity that's what you will read in um in more academic writing about algorithmic problems I thought it's useful maybe to mention this now we haven't talked about this we haven't talked about this so these are both results I just claimed that these are known but we'll we'll actually cover them today it's not uh it's not so far away