Getting Sorted & Big O Notation - Computerphile

Key Takeaways

today we are going to be going over some some basic sorting algorithms simply case so you have a list of numbers and you want to sort that into numerical order and there's all sorts of reasons you want to do that say you've got a spreadsheet open and you want to sort one column that use a sorting algorithm but also there's the less obvious applications all sorts of artificial intelligent stuff if you're playing a computer game and there's some sort of AI somewhere there will be somewhere that they'll definitely using sorting to find the best way to go about doing something let me explain how bubble sort works it's got some playing cards here so I'll just tell you I'll deal them out upside down so I can't see hopefully won't come out sorted so we've got five three seven eight okay so this is actually quite a boring bubble sort you go through the list you compare each pair of elements in turn and if you need to swap them you swap them so you need to swap three and five yes because three is lower than five okay so we swapped those over then we look at five and seven - we've swapped those there we don't seven and eight three sort those no we don't let me go back to start based and Tweenies swap three and five no five and seven no seven and eight no that was very simple very easy once we've gone through the list one full time and there's no swaps we know the list must be sorted so I'll show you that with a few more cards okay so let's deal out three four five six seven eight cards okay so we start from the left do we need to swap seven and three yes doing you swap seven and ten no do we need to swap ten six yes ten four yes ten and eight yes ten and five yes ten and seven yes okay let me go back to the start to need to stop three and seven no seven or six yes seven or four yes seven and eight no eight and five yes eight and seven yes eight and ten no that's the start three and six no six and four yes six and seven no 7:05 yes seven or 7 no 8 and 7 no 8 and 10 no practical start 3 and 4 no 4 and 6 no 6 and 5 yes 6 and 7 no 6 and 7 no 7 and 8 no 8 and 10 No back to start three and four no four and five no five and six no six and seven no seven seven no seven and eight no eight and ten No so we've sorted the list I took a lot of effort and if you had even more cars it would take even longer you can't actually make bubble sauce slightly simpler so let me just do a quick first pass over this so swap those don't swap those that's all those dents all those don't stop those do swap those do swap those what you do now is after every pass the highest card will definitely have been swapped all the way to the end so actually you don't need to check that one anymore you can move that off and just go right don't stop those no those no those no those no those no those yes okay so now you know eight is actually the next card there but it's still not a very good algorithm I can demonstrate merge sort to you if you like so for that I have got another prop we bring in this so I'll deal out seven cards the merge sort we split the list into two parts okay so we've got this left half goes there and the right half goes there we've got two lists now this list gets put into to this let's guess listen to two and then each of these four lists gets put into two until you've got either one card or or no cards in your list now what we do we look at each of these pairs of sorted lists and we merge them back together in the right order by looking at the top card on each list first of all we put four and then we put seven okay so now we've that's a sorted list there okay so with ten and eight we look at the lowest card put that in first we've got eight then we've got ten and then this one we've got five and then we've got seven but these two we've got three and the empty list so three just goes there hopefully everyone will agree that a list with just one card in it is sorted I've separated them just a clarity so you can see the cards you should only bear to look at the top element at each list so now what we do we merge these two sub lists part together which is the lowest card between four and eight those are the two we can see so we pick four I goes in that list and then we say which is lowest between seven and eight it's seven which is lowest between eight and nothing it's eight and then similarly ten and nothing it's ten and then look at these two lists we take pick the lowest so we've got three and then got an empty list so we just put five there and seven there so we've got two so to lists now and all we do is merge them back together so we've got four here and three here so threes lowest so that goes first between 4 & 5 5 & 7 & 7 7 & 7 8 7 8 and nothing it's 8 and then between 10 nothing it's 10 I did three tests we've got bubble sorts we've got the slightly better bubble sort which is the one where you check less elements each time because you know the highest ones are already sorted so we can see that actually around the low end mergesort can be significantly slower than either bubble sorts and that's because most thoughts got slightly more overhead associated with it and also I guess the lists are more likely to be sorted or nearer sorted when they're smaller so we've got the input size here so I sorted 10 things in this row I run it a thousand times for each so a thousand different randomly sorted lists so it took three hundred ninety one ninety seconds sort 10 things with the first bubble sort 322 with the second bubble sort and 770 with merge sort even though merge sort should be quicker there's going to be a little bit of overheads it's a slightly more complicated sorting algorithm however as the input size gets bigger if we're get to 100 say bubble sort to twenty eight thousand nine eight seconds the better bubble sort took nineteen microseconds and know sort took about eight microseconds so you can see there that the merge sort Saul ready starting to take over even by 100 so let's see what it's like at a thousand bubble sort is taking three milliseconds to sort this of a thousand things the better bubble sort to take in two milliseconds and merge sort is taking 0.1 of a millisecond to sort the list with a small end it doesn't remake with difference but with a big end makes it makes a world of difference really important okay so at five thousand it was taking seventy seven milliseconds to sort with double sort 51 milliseconds sort of the better level sort point six five the millisecond to do those sort bubble sort as I said earlier scales with the square of the input size so they're going to call the emphasize n so we can say bubble sort scales with N squared merge sort that we've just done that scales with the input size times the log of the input size a log is it's just the inverse of a power if you've got 10 to the power of 3 say is a thousand log base 10 of thousands 3 whatever the base of the log is it just is just a constant factor in front of it and that doesn't matter motor sort will always take n Times log n runtime so in the best case and the worst case and the average case you've always got to split the list into two and into two again and two again and then you still want to compare them all immersion about together so that one that one that one that one so you've kind of always got to do the same number of steps the best case of merge sort is still n log n whereas bubble sort what actually what you'll find is if you've got a list that's already sorted it will only take n steps to do it because all it's doing is goes doing sort these no don't need to top these no don't need to sort these no okay so you've done basically n steps so it's proportional to number of cards don't is duty swap so you're done but if you want to sort a list with a million things in bubble sorts not the way to go you need to better succinctly convey how when I wear them scales there's some mathematical notation used by computer scientists this is called Big O notation so actually what you might find is your actual algorithm might run in N squared plus 4n plus tens but what you don't write you don't write N squared plus 4n plus ten you can just chuck away the lower order terms so you just take the term the scales biggest so you can cross off those and you just say as o of N squared okay and the reason is as you increase n the N squared term will always dominate for n so if n is 1 we get 1 squared which is 1 plus 4 times 1 which is 4 plus 10 so you can see this term is actually the biggest one and then this term is biggest and then the N squared times smallest but if n is 2 you get 2 squared which is 4 you get 2 times 4 which is 8 and then we still got 10 but if we make n 10 you get 10 squared here which is 100 we get 4 times 10 which is 40 and then we've got 10 here but as n gets bigger the N squared term it dominates the rest of it the N squared term really takes takes precedence over the others with Big O we only care about the highest order term so N squared so is it a way of saying there is stuff that goes along there might be other stuff but it's a way of simplifying it when we're looking at the figures from my tests or and you know merge sort of it's slower actually at the start than bubble sort that's probably because there's some big constant factors in there or some overhead that is making it take longer there are some algorithms that scale the order of n factorial is n times n minus 1 times n minus 2 times all the way down to one got N and n factorial n is one n factorials one n is two it's two it's three we've got three times two times one which is six when it's four we've got six six six six 720 but seven it's whatever seven times by it is quite a big number by the time you get to 70 factorial my calculator doesn't like it because you've gone over ten to the power of 100 I can show you a sorting algorithm that in the average case is n factorial if you like so we've got some cards you throw them up into the air and pick them up we check if they're sorted so are they sorted no right so so chuck them up in the air again and once more pick them up are they sorted no we could be here forever but in the average case it's the factorial of the number of cards so we've got seven cards here so let's go it's going to take me a long time called BOGO salt by the way interesting though BOGO sort has got a best-case complexity of n because if the list is sorted you check if it's sorted and these so you finished you've only done n steps there's anything that you know I've used bogus sorting and practical I don't think so I think the term was invented just to just as just the sort of instructive purposes so you can kind of have an example of an N factorial algorithm I mean you'll find it in practice quite difficult to write any algorithm that runs an N factorial it's difficult even if you're a really bad programmer you'd struggle you probably ought to be quite good programmer to work out how to do something that runs it runs that badly