Video 3-1: §3.0 Sorting introduction

0:00 Introduction

0:05 so welcome back to com526 and to unit three we'll talk about efficient sorting in particular uh sorting sorting lists of things um as fast as possible on a computer

0:18 Learning Outcomes

0:22 there's quite a few learning outcomes for this one but these are just spelling out many little things so we'll talk about merge sorting quick sort because these are the the efficient sorting methods for sequential and in memory and i think it's worthwhile for you to know the performance characteristics of these then we'll briefly talk about the single lower bound where we where you usually touch base on in undergrad classes this comparison based lower bound for sorting and we'll see how to beat it

0:58 then i added a new a new section about adaptive sorting we'll talk about then about parallel computation first in the context of sorting and later also in the context of other problems so how can you make use of all the multi-core machines that we have

1:22 Overview

1:25 here's an overview in terms of the topics and well we'll go through those uh one by one so uh they they parallel the outcomes i don't think i want to repeat myself

1:38 Motivation

1:42 i want to motivate very briefly before we start why we should study sorting in the first place uh one one fact that um i'm not sure uh you are aware of uh it's a it's an unsolved problem to a certain degree even though every programming language comes with a sorting implementation and sorting is generally fast i mean it's not a um not a big problem if you need to sort your data first you can usually do that in a reasonable time if you want to look very closely from a more eternal truths perspective what is the best possible sorting algorithm that would be one that has the minimal number of comparisons and that's still an open problem uh last progress on this is from the 1950s

2:32 small bits and pieces have been added to this but the fundamental algorithm that's best possible in this sense that we know is 70 years old that's maybe surprising at least i always find this to find this kind of cool sorting of course is a building block for many other tasks so if you can sort fast then other tasks inherit that speed it's often convenient to pre-process data that way or it's just part of a bigger algorithm for example many algorithms that work with multi-dimensional data they start by sorting data according to one dimension and then work from there and so and they do this multiple times apart from that it's a it's a nice playground to test out some of the theories um it it's me of manageable complexity in many ways after all it's just bringing a list in into order that's a problem you can explain to primary school kids but then applying the the more advanced techniques to make this really fast on a computer is still still active research all right

3:48 i want to focus first on some classic methods that some of you will have seen and for others i'll go through them quickly so that you've all seen the same version of them at least um i will briefly talk about some some personal pet project of mine um but also beyond that how to exploit it if your list is already somewhat ordered and then the big topic about parallel computation

4:17 Sorting

4:25 for the first part i want to make sure we know the rules of the game as i called them here and this is also setting up the notation for for the algorithms that appear on the slides so we start with an array of objects and again um in python you don't really have a race so it would be a list for all intents of per and purposes you know from unit two uh python lists are still a race even though resizable ones uh but the important part is we have an array where we can access the ith element or any i in constant time and we can overwrite it what we cannot do is insert something into the middle of the array because that would really mean copying many elements over all right the second assumption if we want to sort objects we want to be as general as possible so i don't want to say we're specifically just sorting integers um not at this point we want to sort arbitrary objects and what i need for that is if i give you two objects you tell me which one is smaller and you can decide what smaller means for you uh it's in in libraries or in in programming languages there's different ways to do

5:36 this in python you can sort objects of a certain class and there's a way to overload this built-in operator less or less or equal by by implementing this function which obviously stands for less than so i guess it's the strictly less uh and in java there's there's um an interface called comparable that has this method which again allows you given two objects decide which one is smaller okay so this is something that all libra all programming languages and libraries allow you to do you give it a list of objects and you also tell the sorting method how to compare objects

6:28 we'll usually think about sorting in place so we're given the array and we modify the input that's why it says rearrange or permute the given elements and well of course at the end it should be sorted which means whereas the smallest element is on the left and then they start they increase so it's ascendingly sorted

6:49 for the first part we assume that the array fits into main memory that's um that's an important assumption because it means that different algorithms are efficient and we use just a single processor but we'll come back to that at the end the rules of the game good so far

7:11 Complexity

7:14 i wanted to ask you to also guide me how quick i want to run through this what you've seen about sorting in the theoretical side of it so the question is about the complexity of sorting and take it

7:31 as you think this is meant when i say complexity it's not necessarily completely well-defined i don't know where this picture picks pictures shown at all just ignore it okay i'm confused by slido but here's if you want the you can pick one from the list uh try to be as precise as possible though

8:48 that's not the question it's the question what is the complexity of the sorting problem i'll explain what i mean by that but the questions well defined as is um in my definitions

9:10 anyone still busy see a few people typing um let me show answers uh so there's a big blob for this one and in a sense that's almost correct uh let me very briefly remark on the on the question so this is a bit of an aside and not the main focus for this module we'll mostly be talking about concrete algorithms and how good they they do how well they do but you can ask about the complexity of a problem in this case the general problem of sorting a list and then what people mean by this is first of all uh in the worst case it's usually the assumption and asymptotically for large n as usual and ignoring constant factors as usual so we're talking about theta classes now the complexity of a problem there are two sides of it there's

10:14 a lower bound how good can it possibly be solved what's the fastest conceivable method for sorting and there's upper bounds these are algorithms concrete solutions that have a certain running time ideally in in the in the again the eternal truths worlds we can find some things that match here so we know a lower bound and an upper bound and they're in the same theta class then we can say the complexity of the problem is solved and is theta of whatever it is okay now for sorting we're actually in the situation of being able to say that it's uh it's theta and log n uh if you define sorting to be comparison based sorting we'll cover this uh in more detail uh because you can't see this in this world old picture uh there were eight votes for order n log n for this big one which looks much bigger i mean than eight out of fifty four if you ask me uh there's five more words for theta of n log n and then there's votes for the for the answers and i don't remember which one was which so g got another five and h is this one got three and where's theta and again i

11:36 not so many votes for i it seems with it on the list can't find it no one voted i seems so okay yeah so don't worry uh this is just out of interest um i think questions of this type are usual useful to have in mind but i take it that not so many of you have seen the question formulated in this in this way

12:18 yeah so we'll touch in this module on both sides both the lower bound and the upper bound and this is one of the lucky cases where we can completely settle the complexity of the problem and that's where the theoretician says oh job done i'm going home from a practical side of things this is sometimes not the end of the story because it leaves open whether the uh constant factors are the same in the lower bound in the upper bounds or even if if any of the algorithms that we have has a reasonable constant factor factors that it is useful in practice and it sometimes leaves open other things like is this only a problem in the worst case and if we relax that a bit we can improve the algorithms so from from our perspective where we take a look at yes eternal truths but also uh things that are useful and effective in practice will not stop at saying and log n is the answer