okay this is nastinovsky we're doing analysis of algorithms chapter seven which is all about quicksort okay so we finished heap sort and we saw heapsort in the worst case scenario is then login that's very good now we do quick sort quick sort i think was the first algorithm that really got it below n squared and it's considered it's a it's a great algorithm it's an important algorithm okay a lot of the ideas we have about things in chapter 8 and chapter 9 will be using quick sort ideas so it's an important algorithm to do the only problem is it sometimes can be n n squared but most of the time is n log n also okay now we studied already merge sort quick sort is is in a certain sense merge sort stood on its head upside down and i'd like to explain to you what it means okay in merge sort we easily split the numbers we take the numbers we split it in half just chop it in half okay and then we sort the left side sort the right side and then we slowly merge it together okay by slowly i mean it takes n to bring together two sorted arrays to bring them together is n okay so easily split this is merged so easily split spend time combining it as opposed to that quick sort we spend time splitting it we're going to spend most of this chapter talking about how we're going to split the car split the split the numbers but then it's easy to combine so you see this is a flip okay let me just show you quickly um the way the algorithms work the difference between merge sort quicksort merge sort your first you just chop the numbers into half and over two if you have an odd and over two floor okay sort the left side merge sort the right side and then slowly merge them together that's what that line is all about okay quick sort is going to be slightly different i'm sorry really different it's gonna you're gonna take the n numbers and you're gonna partition them and some numbers are gonna be over here and some numbers are gonna be over there and then what you do is you quick sort those numbers you quick sort these numbers and then it's going to be easy to bring them together you'll see it in a minute but the main point is here you do the first the the merge sorts and you slowly bring it together here you'd spend time partitioning it and then you quickly sort then you know bring it together okay on average this is going to be n log n the worst case scenario this is n log n quick sort on average is n log n but in the worst case it's n squared okay in the worst case it's n squared but it's very rare for it to be n squared and we'll talk about that at the end of this chapter okay so the main hard part of quicksort you see this is just recursive recursive the quicksort quicksort calls itself so this is the quicksort algorithm by the way it is a three line program as opposed to heapsort and merge sort well mergeload is not more than a three-line program well merge is a large thing partition is a large thing but the the sword itself is a three-line program so that's why it's very popular but the partition part we're going to spend most of the time talking about the partition so let me show you that stop okay so this is the partition algorithm this is the algorithm that splits things up it's a little bit painful so we're going to go through it line by line so but basically what it does is it takes your array here's your array a which is part of the input it starts at p and ends at r so this is array a starts at p and ends at r and it splits it up into two parts those things less than the pivot those things more than the pivot the pivot is right here okay and basically what happens is it goes through the array like this this is position j okay all the elements in here are less than or equal to x all the elements in here are greater than x okay and in here is not seen yet okay so we start off here and we didn't see anything and slowly but surely we're going to pivot so x is equal to a of r that's the last element we're going to pivot around that element and put those things that are less than x in here those things that are more than x in here and then keep on going until we get to the end and then again what's going to happen is you're going to split the array is going to be split someplace all the things less than here are on this side all the things more than here are more okay so let's go through it partition a is the array p is the starting point r is the ending point x is equal to p of r that's the key that you pivot around that's the thing that you split the array into two okay i is equal to p minus one so you start off on this side and you do as follows for j is equal to p to r minus one you pretty much go this j goes along from the beginning till the end till x we don't have to we don't have to check around here and here's what we do if a of j that's the thing that you're looking off as you go along if it's less than x then here's what you do move i is equal to i plus one i was over here now move it over here it's that's your boundary between what's less than x and what's more than x so if you found something that's less than x you have to increase your boundary and put it in this part then you exchange a of i for a of j we'll do it with cards in a minute okay and you keep on going and keep on going okay those things eye is at places where it has to move it to this side so you're going to see as we go along at the end at the end it's going to look something like this you're not going to have anything not seen anymore and so what at the end you're gonna have something like this here's your i position all these things are less than x okay um and all these things are more than x and at the end you swap this put x over here so all the things less than x x all things more than x okay and this is going to be something that's more than x okay and you do it okay so let's let's do it with these cards uh here i have five let's pivot with these cards so basically we start here i is here p is here we're pivoting around five so five is our main card question is three less than five yes it is so what do we do okay well basically i is equal to i plus one we exchange i and j well we're going to change three for three three is less than five we leave it alone okay is six less than five answer no it's not 6 belongs on that side but we don't do anything now we do 7 more than 5 yes 7 belongs on that side that's fine okay now let's do this is so basically this is our boundary this is our this is our i is two more than five no it's that two is less than five and so what we do is we swap it we swap it with what with six and 2. we swap that okay that's this exchange let's go on 10 is 10 less than 5 no it's more is 8 less than 5 now it's more is 4 less than 5 no it's 4 is so what we do is we swap it we go like that king and queen is more than five so we leave that alone and then the last thing you do is your eye your eye is over here that's the last thing we change you swap it like that okay now when you look at this you'll see these are things that are less than five not necessarily in order these are things more than five not necessarily in order and so we're not going to bring them together it's not going to be in order we're then going to quick sort this and we're going to quickly sort this the main thing to keep in mind is that when you're quick sorting your pivot element is very important for example if i pivot element this with this six i'm not going to do very well basically at the end this will go here and everything here is more than six there'll be nothing less than six so we're going to do another example of this partition algorithm it's a very nice algorithm question how much work is done well basically what you're doing is you're doing this loop from the beginning of the array to the end of the array or the end of the array minus one okay and so you're doing it so and each time you're doing basically just one exchange so this operation takes this this program takes nine end times okay i don't want to do it with that i want to do it with this okay so let's let's do this we're going to pivot around eight five is less than eight let me make sure that the camera can see you guys holy cow sorry okay sorry that was a big mistake okay guys now we have to do it we're going to pivot around eight okay sorry about that i'm not gonna mess it up pivot around eight so um five is less than eight leave it alone seven is eight less than eight leave it alone king is more than eight so it goes on this side that's fine queen is more than eight six is more than eight three [Music] okay anyways what's going to happen is this is going to go upside seven is more three is going to go here we're gonna swap at that queen is gonna go there two is gonna go there okay and ten is gonna go nope 10 is okay okay then when we're finished we're gonna swap it like that okay anyways you're gonna see it working in in the algorithm okay so that's partition and then so again you have to go through it i'm sorry i messed up the first time but you'll you'll follow it basically it it's it's not so so bad okay then the quicksort algorithm is as follows just doing it um i i wrote it already but i just want to do it a little bit more details if p is less than r that means if the beginning of the array is less than the end of the array then q equals partition a comma comma r quick sort from a the array a from b p the beginning till q minus one okay there's no reason to partition the the pivot and then quick sort the other part a comma q plus one all the way till r that's it okay how much work is done very simple on average well it depends how much you pivot how much you split it into okay so let's see what happens in a good case in a good case you'll pivot around something somewhere in the middle so you'll have something like this you'll do n operations in order to partition and then you're going to have t of n over 2 for the left side plus t of n over 2 for the right side okay we've seen that before you've seen that a few times before that's equal to n log n okay but you know what you could get a bad pivot what happens if you pivot around ten so then on this side you're only going to get jack queen king on this side you're gonna get nine cards so that's not very good but let's see what happens then well in that case it's going to be something like this let's say you do a lot of pivoting you do a partitioning algorithm so it takes you end to do a partition out really but it turns out that after you partition you get something like this one tenth of all your stuff is over here of all your cards over here and nine tenths of all your cards are on this side now you're gonna have to do a lot of work on this side that doesn't help you a lot because most of your cards went out so you can think of it like this you have a giant set you have a few things here and a giant set over there so now when you recursively call it these things get smaller but if you have a bad pivot it doesn't really work okay so this is called a bad pivot the book spends a little time not really in our sections that we're responsible more in section in the later sections um section 7.4 where it shows that even in such a case you know what that's still even in such a bad case where you have bad pivots it's still n log so that's an amazing thing because even when you have bad stuff still things work out well it's very nice okay but you can have it really bad let's say you have end cards okay and you pivot and on this side you have one two three elements on this side you have n minus three elements so only three cards here and here a lot of cards n minus three cards well it's going to turn out this takes a little bit to sort but this one is going to take you have to split it up now again let's say you have bad cards you have a bad pivot here and you only have one card here so this is going to be n minus four cards okay so in this case what's the worst thing that can happen the worst thing that can happen is you have n cards to sort you partition them time n takes you n things just to partition them and the worst thing that could happen is you have t of n minus 1. you don't get anything on this side and you get something n minus 1. well we did this example this was the first example we did it turns out this is n plus n minus 1 plus n minus 2 plus n minus 3. this is the gauss trick and it turns out that that's equal to n squared okay so that's n squared okay so quick sort the worst possible thing can happen in quick start is n squared that can happen can we protect from that okay it can happen n squared but it doesn't happen often so again on average quicksort is n log n in a bad if you have bad partitions it's still n log n but in the really worst worst case or in very bad cases it can be n squared question when does the really bad case happen okay so let me show you let's say i have a bunch of cards okay can you see the cards yet you can see the cards let's say you have a bunch of cards and they're kind of in order then i want to add in two new cards so here's what i do i place the two new cards in the beginning and i say you know what let's sort it right now okay so this is a typical thing you have a you have a list of your customers in your in your in your for your store that you're buying and every month you go at the end of the month and you add in all the new customers that you have and you add them to your list so you have an alphabetized list of customers okay so you have add in a few things now if i pivot with this card i am not doing well why because it's going to make everything less than the king and and a few things more so updating an ordered list and then pivoting with your last card doesn't make sense because your last card is your maximum card you're not going to partition very well if you use your maximum card so quick sort is not very good at maintaining a list that's almost already sorted okay so this is what we said we're not only analyzing out we're not only showing algorithms we're analyzing when is it good to use it well it's not good to do that okay in contrast if the thing was totally unsorted then you might want to use the last thing okay so that's an interesting thing that quicksort can have the worst possible case can happen when it's totally sorted or when it's very close to sorted that's an interesting thing okay now here's a solution the solution is in section 7.3 it's called randomized versions of quick sort let me show you what that's about okay but beforehand let me just give you a brief overview you see computers are very good because they do everything exactly as they're supposed to do they're deterministic you tell them to do things it doesn't it doesn't flip a coin it doesn't you know randomly think about things and stuff like that that's what human beings do and so that's the power of computers they do things in a set way but we're going to see something actually very shocking okay here's a bunch of cards and you can see the cards okay if i use this as my pivot card it's not going to be very good because it's 10 it's a high number so in section 7.3 they make the following suggestion randomly pick another card randomly pick another card exchange it with the last one and now do random randomize quicksort now do quick sort right there that's called randomize quick sort you don't choose the last card as your pivot you choose a random card thinking that the random card you choose might be somewhere in the middle okay and in fact five is somewhere in the middle so it's going to split the cards halfway through okay what can go wrong here okay so again the purpose of doing that is you're going to split the array better than if you have a bad cut than if you have a bad pivot okay what can go wrong well i can randomly choose a card and i'll choose this one the king is over there now if i use that king what happens if you use the king it's not going to have a good pivot so randomize even using the randomized thing you can still have the worst case scenario and in the worst case scenario it's an n squared algorithm so again quicksort is n log n on the average case in the very worst case it could be n squared there is a way of preventing the n squared by randomly choosing some card in the middle and you think that if you randomly choose some card in the middle you could maybe do better okay but even when you randomly choose some card in the middle you can still get the worst case why if you randomly choose the king or you randomly choose some high number from the middle okay so here's another suggestion this is mine it's not in the book but it's not mine here's another suggestion you have an array you want to pick some card that you know that when you partition it won't partition so rather than picking one card over here by random and then pivoting around that one card why don't you do the following pick three cards okay so let's say this is six this is um eight and this is five randomly pick three cards okay then put them in order choose the middle one what's the middle between six eight and five and the answer is six okay now put that in the at the end the one at the end put that at the end and pivot around that card why because you chose three by random what you're going to make sure is probably you're not going to get by using the middle one you're not going to get one of the closer ones okay and so you're going to get something that's far away from the extremes either one ace or king okay obviously this can also backfire but it's gonna be a lot harder to backfire if you randomly choose three cards okay and they happen to be jack queen and king and then you're gonna pick what's in the middle of jack queen and king and the answer is queen okay and you put the queen at the end and you pivot around the queen that doesn't help you but the chances of randomly picking three cards and all three of them are such high cards is very very rare so again quick sort is an n log n algorithm and it works very well okay it can get in the worst case n squared but we have ways of protecting it to make sure that it won't get to n squared unless really bad things happen anyways so that's that next time we do chapter eight chapter eight is called sorting in linear time not n log n but down to ed show you have a great day