Video 4-0: Sorting Intro

0:02 In the next unit, we'll talk about sorting the one of the most fundamental problems in computer science. And let me switch to the outline uh for the next part. We'll look at only the two interesting methods. I'm not going to bore you again with quadratic sorting algorithms because they're by and large not very useful. uh but we'll look a bit at uh merge sort and quicksort as the two main practical methods and then we'll dive a bit into the theory behind sorting that's uh I only alluded to in algorithms and data structures I want to set the stage here also for what we use in later units and lastly a bit of um practical aspects of sorting what can you do when uh the input is already a bit sorted it and some indeed uh all the way practical to implementations in in libraries. Some comments on that. Why still study sorting? Let me try to motivate this a little bit. First of all, you need to know some of these algorithms because they're kind of the language that people speak is also one of the fundamental problems of computer science that are still not solved. Maybe shocking to hear but uh we don't have an algorithm that uses the precise best number of comparisons in the worst case.

1:26 Um this is even the number of comparisons that you need for this worst case is only known for certain values and then unknown. We have some bounds we'll come back to that. Um but there's still some parts open. And in the slides I had to update these again. there was uh a a niche breakthrough in this area that uh is new and wasn't like was open for 60 or 70 years you could say. Um it's a bit the proof is unfortunately a bit impenetrable but it seems correct.

2:04 I'll come back to that as well. Apart from that practical motivation is it's used all over the place as a sub routine because sorting is is cheap and efficient. you might as well do it in before you do some other tasks. We'll see a good example next unit about that. And so um it's it's worth knowing from that perspective and it's also a good playground for practicing some techniques that are more general.

2:35 Let's start with the basics and all of the algorithms in this part uh the the basics part have the following assumptions. We're given some array of objects and I'll try to be somewhat careful with either calling these objects or elements. And I'm not going to say what they are in particular. They may be strings or integers or or other numbers or maybe database records or rows in an Excel sheet. This shouldn't matter because all we need about them is a a total order. So given two such objects, I can tell you which one is smaller. That's the assumption that also our programming languages make. In Java, you have uh objects that are inheriting this comparable interface and then they have a method compare to. Uh in Python, you can override this um less or equal operator by implementing this double underscore less equal double underscore method. Uh beautiful syntax um for for specifying it. But then you can just use the normal operators and that's the only assumption we make.

3:48 Um the reason for that is this is convenient to use and convenient to build algorithms for. If you build your custom objects, it's usually easy to build a function that compares two. So it's it's rather versatile and as you'll see it's it suffices for fast sorting algorithms. Uh what is sorting? Maybe needless to state, but let me do it still. We're given initially these elements in some array and we want the array to be sorted. Um so we want to permute the elements. It should still contain the same elements this array after we're done just in a different order so that they're weekly increasing.

4:34 There's different flavors of sorting. Uh we'll look at the case that this array fits in main memory and we are allowed to move things around in main memory. And we do this only sequentially. Uh both of these things we may uh look a little bit into what happens if you do uh different regimes. Not for here. Um let's start with this one.

5:13 This question asks about two things that in a way I both haven't told you formally. It asks about sorting obviously and the the answer it also asks about what is the complexity of a problem. I don't think we've spoken about this in in this module.

5:37 So the question is my excuse to talk about it. Turns out there's a surprising variety of formatting essentially the same answer. That's that's fun.

6:18 I'll give you a few more seconds without being influenced by other people's answers. Let's reveal it. So the big the big entry uh there's there's two people who sent this one slider is always a bit ah you can see okay you can see it on your phones um thanks so the the big entry here stands for two votes for the same thing and the others are single votes I always feel this is a bit exaggerated either way uh theta of n log n is is the answer I was looking for um and the point is twofold. First of all, uh n login will be or theta n login will be the complexity of these of these two algorithms quicksort and merge sort with a little bit of an asterisk to it. Um but there's more in this question. So when we say complexity and of not this is not an algorithm sorting right this is a problem an algorithmic problem. So the complexity of an algorithmic problem consists of twopart answers. Uh one is a lower bound that says every correct algorithm needs at least so and so much time. We've seen this in the the subarray sum problem there. The lower bound was kind of very simple. It said you have to look at all the numbers. So you need linear time.

8:13 The lower bound uh and an upper bound which is an algorithm. So this one is a proof that says all for all algorithms that solve this problem the following is true namely that they have some lower bound on the running time. So say here omega n time for this sub subarray sum I'll swap this and an upper bound is one concrete algorithm or specifically the running time of that algorithm. or the theta class of the running time of that algorithm.

9:24 Okay. And um ideally we have those two things match then the algorithm is optimal in at least the model that the lower bound holds in. And then we can say the complexity of the problem is solved. We know exactly what theta class we should expect. That's the uh typical kind of template of what algorithm theory would aim for settling the complexity of an algorithmic problem. And so for sorting the answer will be theta and log n. But that needs both components lower and upper bound.