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