Video 3-1: §3.0 Sorting introduction

0:00 Intro

0:03 welcome to unit 3 of com 5 to 6. in this unit we will talk about sorting it's a very basic and fundamental problem in computer science that i bet many of you have already heard about we'll look at the results from the poll in a second there's two reasons why i cover it here once it's a it's a great showcase for a more advanced topic that i bet many of you have not seen or not to that extent that we will cover it and that is parallel computing we'll use sorting as the the first example of a problem that can not only be solved efficiently using a single processor um sequentially working your way through an array of elements but it can also be efficiently solved um using multiple cores uh and in fact many many cores and we'll study precisely what are the limits of parallelizing sorting that's something that we will look at later in this class again for other types of problems and the other reason is sorting is one of the topics where there's a very nice and sleek lower bound proof so a proof that no algorithm can be better than a certain quality and that is a unique feature of computer science i think that we have this ability to prove certain things

1:29 rigorously no algorithm can ever beat this this cost and then talk about optimal sorting algorithms and we'll we'll see some so sorting is is a topic where this is easy to do it doesn't need advanced mathematical techniques and that's why i want to show this again well knowing that some of these topics will be recap for some of you i wasn't i was a bit optimistic about the dates and you needed more for unit two let's get cracking with sorting okay i asked you to tell me what sorting algorithms you know and here are your answers

2:18 i see a lot of bubble sorts and we see quicksort and merge sort they're also fairly big so they came up um as frequent answers insertion sword is also well known selection sword okay quicksort with or without a space well yeah i would i would use this one but uh people have different opinions counting sorts an interesting one we'll briefly discuss that good so uh people know a lot about this uh and even politicians might know a bit a little bit about this there's this famous question that barack obama was asked what's the most efficient way to sort a million integers uh if you haven't seen this very very uh funny and impressive um sorting is is well known and well studied so um i i will try to keep the basic parts short as as we've often done

3:18 uh while we're here um there was there was another question um on on the last unit how to convert a normal tree to a balanced tree uh i think i'll have to refer this uh either to a campus wire or actually to the lecture videos

3:37 there's some ways to do this but usually you just start with the balance tree okay so with that um let's start our our unit on sorting so here's a quick overview we will talk about mergesort and quicksort because these are the most well-known and most important efficient sorting algorithms we will not talk about the the fundamental elementary ones like insertion sort um and selection sort because they're um they're not fast enough to be relevant in practice and then we'll talk about this lower bound and we'll talk how to beat this lower bounds uh a very interesting um observation but uh this is i think these are these are the key things that you might have seen those before but i want to stress certain points about this again and then in in the next part we'll talk about how to sort in parallel but that will be for next week then before we get started um i want to motivate again a little bit um why we study sorting some of these things i mentioned before uh it's it's one of the fundamental problems in computer science and it's still uh not entirely solved this is maybe an interesting thing to know you have to be precise about what exactly is not solved but if you ask for a sorting

3:43 Overview

4:41 Motivation

5:07 algorithm with the least amount of comparisons that is not known and essentially in a certain way uh the best known algorithm that that is rigorously understood is from oh shoot is it i think it's 1959 it's it's from the 50s it's before really computers even took off and there has no not been very substantial progress on this but we also don't know if that algorithm is best possible and in fact people um i think people believe it's not it's not best possible but we haven't found a better way so it's uh it's still an open problem in that sense it's also a building brick for many many many other algorithms you will know this from from certain other algorithms that if you start sorting your data a lot of processing becomes easier so it's used as a subroutine in many different things whenever you show something to the user uh people usually humans usually just expect things to be sorted and not be produced in some nonsensical arbitrary order so it's um it's ubiquitous in that sense and that's the point i mentioned it's a good playground to study certain techniques that are also applied to more complicated problems good um that brings us to

6:32 Sorting basics

6:36 part one the basics that's the the sequential parts and that will cover uh the things that you might have seen in in some earlier algorithms class before i want to

6:53 be a bit more formal about what sorting is um as a problem so what what does that look like and a problem in computer science usually consists a problem in this sense of an algorithm consists of an input and an output you're given something and you're supposed to do something with it so we often list this as given and goal or input and output we're given an array of n objects now it's uh somewhat important that this is not specified it can be arbitrary objects that we don't know anything about except that there is an order relation there's a way to compare two objects given two objects i can tell uh which is which is smaller which is bigger

7:41 so it can be an explicit comparison function that's how you would do it in java so there's this notion of a comparator it's a little class that implements a comparison function

7:58 and the sorting methods in the java library they um they can be passed a comparator and then they use this to implement um the order relation on the slides and um in the context of theory we'll just assume there is an is this relation so if you would write in java x compared to

8:24 y we here will just write something like this now okay you have to um okay in java you would write this right but here uh that is the same as just asking is x less or equal y uh just that's just for context if you've used this um maybe it helps and the goal is to take this array uh keep the same objects but move them around in the array permute them so that the array is sorted okay we will assume that this array fits in main memory it's stored in well in the ram and for now for this part one we assume that there's a single processor that is performing the sorting operation

9:17 uh if you have any questions about this setup then please let me know ah dear i have to be careful with clicking the wrong buttons right uh this was one of the questions that came up in the prior knowledge survey

9:24 Quiz

9:39 and i remember the outcome was fairly poor but i also asked it in a mean way in the sense that you had to give there were there were many many answers and some were only slightly not not precise enough not not completely perfect okay so in in this poll uh please don't answer the id etc but just write out um the answer like a a string like this if you if you manage to change your answer um uh please do this um because otherwise the the the clocked uh uh the tag cloud will not really render well

10:34 so again don't don't use the the letters um use the um the string representation if possible uh people are still typing uh so i'll give you a little bit more time on this

11:20 all right 17 people come on guys there's more of you out there i know if you feel like you don't know or you don't know uh you don't remember right now uh just put that in so that i know that um you've you're you're done with the question

11:52 yeah there was a an interesting um clarification here is this uh best or worst case let's say it's worst case okay let's uh let's keep it like that and so here's your your attack cloud of uh how things look like uh i hope this was a big o um theta n squared got a lot of votes um

12:32 oh dear and a lot of small things okay this uh bit hard to read okay um we'll we'll uh i'll just leave it without commenting really much and we'll we'll move on but uh we will definitely solve this question in the course of this unit