Puzzle 9: The Disorganized Handyman

good morning everyone thanks for making it here through the snow and sleet you will be quote unquote rewarded with with a cool little puzzle that has put both recreational value as well as a deep connection to the most popular sorting algorithm or at least the most commonly used sorting algorithm called quicksort and so what we have up here is what I call the disorganized handyman puzzle I this is not a puzzle of my invention but I called it this because I think at some point when I read this I it was a carpenter who had a bunch of nuts and bolts in his bag and they were all mixed up so so rather than having these that the nuts attached to the bolts he was disorganized and the nuts and bolts were separate and then they all got mixed up together in a bag okay now obviously all puzzles are a little bit contrived and so we're going to assume here that there's a hundred different nuts and 100 associated bolts and these two hundred objects are all mixed up into this one bag that the carpenter is carrying and not only that each of the bolts is unique in terms of its size and as I mentioned there is an Associated not associated with each each unique bolt and so as you can imagine the goal of this puzzle is going to be finding the most efficient way of creating some organization in this bag by attaching each nut to the corresponding bolt or vice versa right and you can assume that there's no ambiguity because of the uniqueness of the nuts and the bolts and there's a hundred pairs waiting to be discovered and you can try to make that process as efficient as possible as with all of the puzzles that we look at here there's going to be a naive / straightforward way of doing this if you're going to go ahead and figure that out pretty quickly I'll be going to analyze the complexity of that or how long it takes for a specific example of a hundred nuts and a hundred bolts and then we're going to scratch our heads and try and do better all right and as I mentioned obviously there's going to be some programming associated with this and we're not going to represent you know nuts and bolts in in in in programs or codes we're going to switch gears and talk about sorting once we're done with this puzzle good the only way that you are the carpenter if you're the carpenter's helper have of checking I to see that and not attaches to a bolt is to try it out okay and the nuts and bolts are different enough in size that even if you had your eyes closed or was a dark room you could if they're not attaches to the bolt it would screw on perfectly and if it is if the bolt is smaller than they're not it would just go through and it would be obvious that the bolt is smaller than the knot and if not is smaller than the ball it will also be obvious because the bolt you know wouldn't go through it right which makes perfect sense from a physical standpoint right we've all tried this before we've had maybe not all of you but I've certainly had occasion to to discover pairs of of nuts and bolts though it was never you know 100 of them right but so that's kind of a little bit contrived as I said alright good so the setup is clear we're good on the setup excellent so what is the straightforward way of doing this someone yeah funny back there right we could choose a not at random try every different bolt or choose a bolted random and try every different nut right and we're guaranteed in this case that there is a pairing and so after we do that we can put this paired nut and bolt aside and we've shrunk the problem down to one less than the original problem if I started out with a hundred pairs that are not paired together but there's a hundred knots and a hundred volts then I get one pair which is a correct pair and I have 99 knots left in 99 bolts left right and I keep going right perfectly reasonable way of doing things and I let me show you how that would work these slides were making made by my daughter's many years ago you know back when they listen to me right I have fat chance of getting them to do any work for me anymore but they are busier than they were I guess years ago at least I pretend to be and there you go you end up in this particular example which obviously has many fewer than a hundred nuts and bolts you end up checking this and in the worst case how many comparisons would I had to do but would I have had to do if I had 100 nuts and a hundred bolts in the worst case I would have to I have to do all 100 because I might just have gotten unlucky like I said I mean we're not a bawling this at all I you could probably prune the search a little bit with respect to putting aside not having to do an exact comparison but let's just say that even looking at and not as opposed to even touching it with the bulk that you've chosen is in fact a comparison you know you're just eyeballing it as opposed to physically touching the bolt and not together and we're going to call that a comparison and if you do that and if you make that assumption then obviously you're going to have to look at all 100 knots if you have a random bolt in the worst case okay you might get lucky on average it might be only 50 you're not going to do that type of analysis here so so that's good and what is the complexity in terms of the growth rate of this this particular algorithm if I had n nuts and bolts then I do n comparisons in the worst case to find the first pair and when I say first pair I mean the correct pairing that's associated with they're not in the bolt and you know what happens yeah Kevin you have a question it's it's absolutely less than n square in the in in in terms of numerics the the growth rate is a slightly different question right it's related obviously and so I if you I do this and you get the first pair you now have a problem that had that is of size n minus 1 right and so in this case how many comparisons am I going to make when I have n minus 1 nuts and n minus 1 balls in the worst case I'm gonna do n minus 1 comparisons right and then I keep going down and and I you you could you could argue that at the at the very end when I have two nuts and two bolts one comparison if I assume that this was a perfect set of nuts and bolts that we had all pairs right at the beginning I you you could argue that that that small problem corresponding to two nuts and bolts can be solved using one comparison and you immediately know which not pairs with which bolt and the other one as well but you know let's call it a conformation comparison and essentially say you need two comparisons here and and one here you can obviously shave a number I little bit out of out of this but this goes back to Kevin is right it's less than n square if you look at it numerically but the growth rate is n square because we know that n plus n minus 1 plus n minus 2 better dot 2 plus 1 is n times n plus 1 divided by 2 and sure you could you could take this one off and this would become n times n minus one big divided by 2 but that growth rate is N squared grows as N squared right so if you had a hundred nuts and a hundred bolts you're talking about something of the order of 5,000 comparisons right if you want to do it numerically and it grows as N squared if you had a thousand then it would be a thousand times a thousand was the million divided by two that's five hundred thousand so that is astronomical in terms of its growth you don't want to do that right obviously a contrived problem but n square in general then when you talk about manual labor is is generally not very good so if we'd like to improve this right and I we've been talking about recursion we've been talking about divide and conquer this is not divide and conquer in the true sense in in that it's it you're going to a smaller problem admittedly but recall I said divide and conquer is usually used when you break the problem up into fractional pieces ok which means in merge sort for example we took or the tiling puzzle we took the courtyard and we broke it up into four courtyards so essentially we had four quarters in the case of the tiling puzzle we had two halves in the case of mergesort here we are solving a basically one not in bolt in the original puzzle and then we're going from n to n minus one and so there's many more steps right the one thing to remember when you think about complexity is that when you go n to n divided by 2 to n divided by 4 and then you keep going and you go all the way down to 1 this of course when you go like this there's a linear number of steps but when you do that how many steps do you have to get all the way to 1 in relation if if you start with n how many steps you have if I had if this were this were 64 or let's just take a simpler one if this were four how many steps would I have I would have two steps if this were eight I'd have three steps and so what's that formula logarithm log to the base 2 all right so so that's the power of fractional sizes and this is actually a very fundamental notion that is going to appear over and over if you do any algorithms work or take any algorithms classes that I divide and conquer is very efficient because the number of steps in order to get down to small problems is relatively small it's it's a logarithm now if you broke this up into into three parts and you went to n over 3 etc then this would be log to the base something else in the log to the base 3 so log to the base 2 came because we broke it up in you know it and we went down to half half the size right now remember of course I mean it's not that the complexity here it is just logarithmic it's that you do have two problems this is a function of the particular specific algorithm that corresponds to divide and conquer but in the case of merge sort it's not that we just went from n to n over two belt we went to n from n to n over two but there were two n over 2 size problems and but the beauty of of divide and conquer is if I magically if I magically broke up the N size problem and let's go back to our nuts and bolts into two problems of size n over 2 so each a problem has n over 2 knots and n over 2 bolts okay each problem has I'll repeat that and over 2 knots and over 2 bolts then if I used I and and this is magical right I don't quite know how to do that yet but if I did that then I think about what happens with respect to at these comparisons so I said when n was a hundred I needed 5,000 comparisons for this naive algorithm but now if I did this and I got to n over 2 then I have 50 so I'll call that M equals 50 and then I have another one which is M equals 50 and so roughly how many comparisons what I'd need if I had as problem of size 50 50 knots and 50 bolts using our original naive strategy roughly 1225 right roughly and this would be 1225 and so so that is 2500 so of course I don't haven't quite told you how to do this this is still magic but I was upfront about it but clearly I've gotten an improvement if I have this magic okay and so let's talk about that let's turn this nuts-and-bolts puzzle or the solution to this puzzle and try and figure out a divide-and-conquer strategy which is distinctly different from the brute-force strategy that just reduced by one all right now villa this was just going on so the comparisons in the worst case is what I just said and it grows as n squares so Big O n square means it just grows as n square right that's asymptotic notation that we won't go into but you get you understand what that means now so if I do a straightforward divide and conquer like I did with merge sort where I just took the array and I split it in half right if I take these nuts and bolts and I take separate the nuts out you know put it put 50 on this side 50 on the other side take the bolts put 50 on this side and 50 on the other side is that gonna work no that's not going to work and the reason is if I do this arbitrary partition but then I'm let's say that I take this and the two of you get together your friends and partners and you say let's do this in parallel and save some time you're still going to be counting the number of comparisons and so obviously you also would like to reduce the number of comparisons but you can't even use a helper here in the sense that if you'd split this up obviously this was not fifty and fifty but three nuts and three bolts on one side and four and four on the other side as you can see from this example you I had a situation where the matching not was in one pile on the left for a bolt that was on the right hand side right and that could happen not just for one which would kill the process but could happen for many nut bolt pairs right so we can't do that right we cannot use the straightforward divide-and-conquer approach so so this comes to the first interesting question that we have here which is how do we exploit the fact that all of you are going to help me so I'm the disorganized carpenter handyman and and and I'd like to break this up first into two piles such that I can go off and send one or more of you off and and say okay I can guarantee that this is a sub problem in the sense that the original problem had all of the bolts that matched all of the nuts that were in my pile I want to break it up and do two problems in this is the magic that we have we need to figure out this magic that such that if I give you 50 nuts and 50 bolts and I keep 50 nuts and 50 bolts that you can solve that problem it is a problem I mean it there's there's a matching there right for those 50 nuts you have the 50 bolts in your pile same thing with me all right so how do I do that yeah go ahead Josh no you cannot yeah good question all right so you you you the only thing you can do is you know you have you have a and not in you have a bolt and if it goes through then the nut is bigger if it doesn't then the bolt is bigger and then if it fits exactly you have a match all right great so yeah go ahead you know because it fits in perfectly right if it fits so all the ones that you just go through all the light goes through just the hole then you know those are smaller hole they're bigger right great excellent so banana is discovered this notion of pivoting and pivoting is essentially something that is best described here in animation that gives you a divide and conquer strategy right now I answer Joshua's question and that is a key question and I'm not going to violate the answer to that question I buy I using some other strategy that that does not correspond to this not pull check right so the only thing I can do in this puzzle is a nutball check but I do get three potential possibilities whenever I do a nutball check I do get the information about a perfect match whether they're not as smaller or whether they're not as bigger right and that's all I need in order to do pivoting right and so what's going to happen here is I go ahead and I choose an arbitrary bolt and if I I don't even actually need to find the match before I start this process so it's a small variant on what gonna throw set but it's really a pretty small variant and when I see that this is not a match and in fact the nut is bigger then I put the nut on the right hand side pile okay when I see that they're not is smaller then I put the nut in the left hand side pile and I see a match I just put that aside I don't put it in either of the piles because I'm going to actually it turns out I'm not going to get a pile of 50 and 50 or in this case I'm actually going to get something like 3 & 3 because I'm gonna get one match out of it right so in the case of in general I don't necessarily I'm not necessarily gonna get equal size piles so that's actually a little bit of an issue and we'll get back to that maybe later but I will get a matching and I'll get a pile on the left that is a perfect problem perfect sub problem there I can hand it off to any of you and you can go off and solve it and it'll work and I'll get a pile on the right same thing for that right so this was a match but I don't stop I I don't put the knot in either of the two piles it's just going to stay up there and then I keep going and I make up my right pile and my left paddle right now I'm not quite done yet what do I do now yeah back there that's right so remember I kept the I kept I I guess you used a different term here you you used to I said bold use it's crude that's fine but we're talking about not here so so let's go with the nut and this is not that I put aside I'm going to now compare that not with this pivot bolt that I picked which is now set aside and never have used that again but I'm going to put that aside and I'm going to compare each of the bolts with this this pivot not that I have so the pivot bolt was picked and I discover the Associated pivot nut and I now I'm gonna use that pivot nut which is the the matter that I have up here the light green one and then I'm going to do the same thing and all of this does not violate the answer to Josh's question and it's going to do exactly the right thing I in terms of giving me by giving me two piles that are beautiful problems that are gonna be solvable all right there's nothing that's stopping me from repeating this process then we talk about divide and conquer usually we talk about recursion and we talk about repeatedly doing divide and conquer when I wrote this up here in terms of I the N size problem turned into two and over two problems well each of those n over two problems I could turn into two and over four problems so I can have four and over fours and so on and so forth and so I could clearly do that and especially if n is large then I want to get at reduction in comparisons and get this to grow by the way and we won't do this analysis but rather than growing as n square you'd you'd like it to grow as n log n right and that's kind of the asymptotic analysis that you'll have to do if you take a class like six double oh six but the general sense that you should take away from this is that you're gonna have a logarithmic number of steps and obviously that doesn't imply a logarithmic number of comparisons because the number of subproblems in each of those steps is doubling initially you had a problem then you have two subproblems and then you have four subproblems each of them are are small in size but add together assuming these problems are are n over 2 and n over 2 then you can get something that's substantially smaller than n square a namely n log n ok and you can do that numerically and I don't want to get into that too much but be happy to talk to you about this after lecture or during office hours there's a couple of caveats one of them is and there's no guarantee here if I pick a random pivot bolt that I'm actually going to get n over 2 and n over 2 it's going to be 1 less than that maybe it'd be n over 2 and n over 2 to minus 1 I could get something if I picked a large pivot bolt I might get a very skewed pair of piles right one of them could have 80 in them 80 nuts and bolts in them and the other one could have 20 nuts and bolts in them okay so that's something to worry about and we won't worry about that but we'll talk about it when we move to sorting which is what we're gonna do in the in just a couple of minutes all right so people buy the solution to the nuts and bolts puzzle clearly it's gonna give you some efficiency if you pick a middling size a bolt and maybe you can eyeball that it's a little bit of a violation of what we've talked about but but you could you could clearly I mean you let's assume that that you can make out the difference between you know something that's as thick as this and their finger and then you pick something in the middle and then you can get two large piles that are roughly equal in size from the original really large pile and at least in the at the beginning you could probably get in the context of this puzzle piles that are roughly similar in size right and after that it doesn't really matter once you've broken things up so n is not a hundred but you know n is more like five or ten at that point it doesn't really matter what strategy you use because the numbers aren't very different depending regardless of the strategy okay so so good alright so I promised you a relationship to sorting and obviously we want to do some programming here and it turns out that just like we had merge sort which was a divide and conquer algorithm it turns out this pivoting strategy it turns into a strategy for divide and conquer that is quite different from merge sort but is equally applicable to sorting numbers okay and so let me remind you what merge sort was and then I'm going to contrast merge sort with quicksort which is a pivot based sorting algorithm right so forget about nuts and bolts we're now down to boring numbers integers and we want to just these numbers in ascending order okay so if I have a bunch of numbers and I want to sort these in ascending order mergesort would say I'm going to go ahead and break it up into halves okay and let's just do one level of recursion you know if with all of these things you can always do more but these problems aren't large enough that you really want to do that in this example and the important thing is you just broke it into half you know bit it was easy the split was easy you sliced the list splice the list what have you right and you assume that somehow you can sort this in ascending order in this case it you need to go to that and then you sort this in ascending order so you go like that and then you need to do a merge and we used what we call the two-finger algorithm to do the merge that essentially says I'm going to assume that this array is sorted and this array is sorted and I'm gonna put pointers up at the beginning of piece to erase and I'm gonna do comparisons and I'm essentially going to assume that I have a blank array of size 6 blank list of size 6 and I'm gonna be writing into this blanket ray the result of the comparison that is which one is less in the comparisons so I'm gonna get minus 31 and then I compare 0 with minus 4 and I'm gonna get minus 4 0 etcetera etcetera all right so that was our merge and the important thing to remember is that our merge algorithm was I had an easy divide step and it had a more difficult step at that corresponded to taking the sub arrays that were sorted and and the work was all in the merge okay putting the things together because the divide obviously is just like chop right um now as you can see from the nuts-and-bolts division was non-trivial right division required pivoting okay but there was no real merge after that I mean once I hand it off let's say do you not release 50 nuts and bolts after I did the work in pivoting and I kept 50 nuts and bolts as well we were done I mean he's just no maybe I wanted the nuts and bolts back and I don't wanted to run away with it but it wasn't like I had to process anything that he gave me back right if he paired them up then I didn't have to process that right so um this is merge sort the quicksort algorithm which I'll now describe to you is divide and conquer a two way to divide and conquer at same as merge sort but it kind of flips the the work and it does more work upfront before the division and then this at little or no work at the end all right so what happens here is the way we're going to think about quicksort is we're going to choose a pivot you can have some array here and I can go ahead and just call these abcdefg and I'm gonna choose a pivot and in the code that I'm going to show you we're just going to go ahead and choose the last element we assume that this is in random order you're gonna choose the last element of this array as the pivot right and what did we do with the pivot back in our nuts-and-bolts example we someone what would you do with the pivot yeah yeah just basically spliced around it you compared it with but if we took the pivot bolt and stand in this case of the puzzle you compare it with the nuts here we don't have nuts and bolts we just have numbers and so you're gonna take that pivot and you're gonna start comparing it with the other numbers and you're exactly right in that we're going to get to the point where we have to splice around it which isn't your standard you know python splicing because that requires contiguous locations right but what you want to do is you want to get to a situation where you have something like this where you have G somewhere in the middle and all elements less than G are to the left and let's assume they're all unique elements all elements greater than G are to the right okay so this is exactly a pivoting around G right so this is it's referred to as pivoting around G okay now the nice thing here when you do this and is that you can go off and you can fix the location of G in fact G's location just like the pair the nut bolt pair was corresponding to the pivot nut and the pivot bolt was determined during the pivoting step and you never had to check whether never had to discover that pair again you can put that pair aside the location of G the pivot chosen in the final sorted array is determined by this pivoting step okay that makes sense um and so so this location whatever that indexes you know it might be right in the middle it might be a little bit skewed but that location is determined and if you did this with roughly equal piles if you will or equal sides if there were a 100 elements here you might see you know 50 odd here and you know 40 or over there right and of course if G happen to be the largest number then G would be all the way to the right right so so there's that 20 month and so but this is the divide step so the divide step is the pivoting step and then you can go off and sort its each of those sub lists right because those less than G are not necessarily in ascending order right you just you know dump them there's still work to be done and then the greater than G likewise they're not necessarily in ascending order but I you know that there's 42 elements in corresponding to less than G and you can go sort that array and those are going to be the first 42 elements of your final array right and the G is going to be at the 43rd position and then the ones that are greater than G are going to be to the right of that all make sense right yeah go ahead Fadi that's right so that's pathological now it turns out that amazingly I in order to avoid that situation when people use quicksort in practice which is essentially this algorithm that I described they take the array that they're given and they actually randomize it they actually make it they shake it up right it's it's like you get these nuts and bolts and you want to close your eyes and you want to pick up and not that's middling in size and you know maybe all the small ones are up at the top and the big ones are down at the bottom you want things in the middle so you go to shake shake shake you know you randomize and then you go stick your hand in but halfway through the pile and pick out pick up enough I'll pick up a ball right that's kind of what happens here so so quicksort it turns out and I'll just say this and if this doesn't make sense ask me later but it should give you some intuition I the random randomized quicksort where you have this random input and you have some probabilistic guarantee that you're picking a pivot that is middling in size in terms of an integer size is going to be n log n in complexity but the worst-case complexity of quicksort is actly as you said it's n square okay but you know that's really not something that you need to understand deeply to understand about either the puzzle are the rest of this lecture you do get a sense of as long as you have a sense of if you pick something in the middle and these piles are roughly equal in size I'm gonna get some improvement right the guarantee that the piles are roughly equal in size all the way down to the depths of recursion is a difficult one to achieve in a deterministic way but it's not hard to achieve in a probabilistic way right by doing this randomization you had another question yeah that is the rest of the lecture okay which is only 10 minutes left but okay so that's the that's the rest of the lecture right so one of the things that I said here I said a blank list of size six okay so what merge sort requires in order for merge sort to be efficient you needed auxilary storage that corresponded to at the size of the list because right at the first level of recursion and when you got to erase that were n over 2 and n over 2 and they were both sorted and you had it I had to merge the two together to create the final result corresponding to the sorted array you ended up requiring storage that was N in size in order to actually do this two-finger algorithm and compared the minus 30 ones with the zeros and then write them into this array right now the obvious way of taking this and going to here is code that I'm going to show you that is easy to write and it requires a blank list as well okay you just I mean the easy way to do that and I'll just show you the code because it's easier to show you the code as opposed to waving my hands here and potentially confusing people but let me show you first the quicksort divide-and-conquer which is abs totally trivial I mean just like mergesort was but pivot partition is this step here okay this is the pivoting step and and this is what that procedure does right so we'll get to that in just a second but the rest of it is simply I'm going to go ahead and once I do the pivot put partition I have something that looks like this and then I just go off and run quicksort on this and quicksort on that and I'm doing that and on the array itself it's it's just like I have this array and I'm just saying I'm gonna call quicksort with the indices that are associated with the beginning and the end of this array and then I'm going to call quicksort with the indices that are that begin with the beginning and the end of this array and as long as and that same array is going to be my final output right so everything is done and at the term that's used here is in place right so in place sorting and insertion sort which is also n square and a few other things are in place sorting algorithms which essentially say look I need to sort all of you if you know in some hour some ran some way right you know perhaps by age or something and um you know I don't want need I don't want another room right I don't want to say he'll who's the youngest here and then go over to that room and then you know who's the next youngest and go over to the room etc I just want you to start swapping positions here and we're all gonna be in this room and somehow you know we're gonna get sorted right so that's in place and when I haven't an array that corresponds to integers I don't want another blank list or blank array and use that storage and so that answers your question at the top level as to why quicksort is used and it's used because the memory requirements of quicksort are substantially less than the memory requirements of merge sort and in fact you can do this a pivoting step using one integer as storage and you need the original array of course but you needed that to store all of the numbers and the auxilary store is the extra storage that you need is exactly the storage for one integer where you store the pivot okay and I'm gonna show you the naive way which is the regular quicksort and and that is that a trivial pivot partition it's not the clever one which essentially says look I'm gonna go ahead and I'm going to create a new array and I are in fact I have two arrays that are less and more or two lists together the sizes of less and more are going to be the size of the original right maybe minus one but I'm adding two less and adding two more depending on whether the element is less than the pivot or greater than the pivot and then I'm good so there's that there's that algorithm which would just be oh yeah I'm gonna create a new list here and I'm going to compare a to G and and then I'm gonna compare you know B to G etc etc all right so this does not give you anything this is an uninteresting algorithm I'm sorry the implementation this is an uninteresting implementation okay it is much more it's it you need to be much more clever I don't need this anymore to do this in place okay so what I want to do is I gonna take an example here I wanted I want to be able to take this array and I'm going to not talk about the recursive sorting or anything like that because that's easy right we kind of know how to do that what I want to do is I want to choose this as the pivot and I want to translate that somehow into the final I pivoted an output which is going to be 0 minus 31 1/2 6599 whoops so I have something wrong here so this should be the other way around 83 right okay mmm oh I'm sorry I'm sorry um this is fine this is fine I just need it I don't need to be sorted okay good whoo all right I had this I I just thought I found the first bug in my book okay so there's probably many bugs in the book but I don't want to know don't write so I don't need this to be sorted yes as a 0 a minus 31 so the key is that I've discovered this and everything to the left of that is less than 1 and everything to the right of that is greater than 1 and that's the only requirement that I have and and as I said I mean I said this to begin with and then I forgot I said we're not going to worry about the recursion so clearly I have to do more work here with with respect to taking this is set of numbers and and sorting them in ascending order etc but what I've done here is I know that one is fixed in place and one will never move right and I just do have you turned this into minus 31 and 0 and I have to do some reordering here but one is fixed in place okay now the algorithm that I have that I'm going to show you I'm going to show you the code and it's probably code that I you won't be able to parse at least in in minutes or seconds and this code is in place pivoting okay it's a clever code and what it does is it has one additional variable worth of storage that we're going to call the pivot right so that you see the variable pivot there and just using that one additional integer storage it manages to transform this array using a linear number of steps into into this array all right so you can see that this is non-trivial right I need to I need to move from here to there without having this extra storage if you had extra storage it would be easy we know how to do that but if you didn't you have you need this this code that has an outer while loop you see while not done and then it's got two inner while loops in it and it's got a couple of counters couple of pointers I should say two indices and you go left and right and you magically get at this answer right but there's no magic here because we have the code up and we can run it and computers aren't smart so clearly that that code is doing something clever and we just need to understand that all right so I'm gonna in the couple of minutes I have left this is the last thing I want to do is I want to tell you how this code works okay and it's really pretty code and it's it's clever code so what I have is I have two pointers top and bottom so I'm going to essentially say that top is all a bottom as zero initially is minus one but we go ahead and increment it and top is eight right and so how many I have nine one two three four five six nine so so so so top is pointing to the pivot so this is this is pointing to the pivot which is top is eight and and bottom is pointing to to the first element right so um these two while loops are essentially going from the left of the array and going this way from the from the right of the array so what we going to do and I and don't worry about exactly how the code does this I'm going to show you the way this array is transformed and the way this these pointers are changed and then you'll get a sense of how this code works right and obviously this transformation happens in one of those while loops all right so we have the pivot corresponding to one and bottom equals zero and top equals eight what I'm going to do is I'm gonna start moving I'm leftward from i this would be the second inner while loop I'm gonna start moving oh I'm sorry I'm going to start I'll start with a bit with bottom I'm gonna increment bottom is initially minus one and increment it to zero and I start moving right word from the left of the list and try and find an element that is greater than one right and that is immediate I realized that four is greater than one okay so when I realize that four is greater than one I'm going to copy over four and this is doesn't mean that I'm copying the entire array I'm just going to copy over four but I'm writing what the array looks like but that's important over to here right and you might say pivot equals one you might say oh but I over wrote the location one and I'm like don't worry about it I do have one stored in my pivot so my pivot has one in it okay so I haven't lost anything here it's not like I threw away any locations I do have that extra location right so I did this right word move going from the left now I'm going to go leftward from the from the from the right and I'm going to look for something that is less than one and I'm going to try and move it so basically what this algorithm does is it it tries to find things that are if a is is greater than G it moves a to the rightmost part of the array if if and the same thing if D is less than G then it moves it to the to the left part of the array so depending on whether the comparison to G is greater or less you want to end up in the edges of the array and you're going to try and get the edges of the array to be correct in the in the sense that they have elements on the left that are less than the pivot and the elements on the right that are greater than the pivot and you try and get to the middle and when you when you're two pointers converge your top and bottom pointers converge you're done all right so let's do a couple more steps and and and close this lecture so I did the right step now I'm going going rightward and now I'm going to go leftward and what is the first element that is less than one I know less than one zero right yes but I'm going this way yeah I'm going yeah I'm glad you pointed that out I needed to make sure so I went I went right word the first time and I want to go left word this time so so this would be so I I come here and I see I see zero when I see zero what I'm going to do is I'm going to transform the array I'll write this out to make sure I get this right and so right now I have 465 to minus 31 0 etc and I'm going to go this way and I'm going to put when I see the zero I'm going to copy over 0 over here and leave the 0 in here for a second and there's no problem here because 4 was copied over here and so now I overrode 4 with zero okay now you kind of see maybe get a some sense of how this algorithm works this is the first interesting step where I took zero and because zero is less than one as I mentioned I want to jam it all the way to the left ok just put it all the way to the left and I'm cool with losing 4 because 4 is being put all the way to the right okay now at this point my bottom and top I'm going to get modified my bottom is still zero but the top is 4 because I moved top was 8 and i decremented a top all the way to the point where it became 4 and I realized that 0 was less than 1 and then I copied over that value over to the to the bottom you can kind of see the code up there it it this is actually an output of that code and I put I put a 0 in here so that's what my counters look like and it's only a couple more steps we're gonna go now go right and I'm going to go do this again except that 0 is already taken care of so now I see 65 clearly I'm going to have a situation where if I go this way 65 is is greater than the pivot right so I'm gonna go 0 65 to minus 31 and because 65 is greater than the pivot I'm gonna write it into what the top was which obviously got copied over that way so I'm gonna have 65 in here 9983 seven eighty two and four alright so now after this step bottom equals one and the reason for that was 65 is in the location on one and top equals 4 and then the next one someone want to tell me what the next one is going to be if I go left word I'm gonna start from here top was four so it's pointing at 65 and I'm looking for looking for something that I when I go when I go this way I saw 65 greater than 1 now I'm looking for something that is less than 1 and minus 31 is less than 1 correct when I go this way I'm looking for something that's less than so so given that is minus 31 I'm going to copy over – 31 – what top was pointing to so I have minus 31 to minus 31 sixty-five 9983 seven eight two and four and at this point I'm gonna have bottom equals one and top equals three keep going one more and I get to the point where I see 2 2 is greater than 1 0 and minus 31 are less than 1 and so I take 2 and I copy your copy it over here all right and now at this point when I do an increment I realize that top bottom is 2 and top is 3 and in the very next step bottom will equal top and I'm sitting up here and so I copy I make 2 I'd write the pivot into the location that corresponds to that bottom after the top got decremented and in that case both bottom and top are 2 and that index 0 1 & 2 the pivot gets written into it and so that's exactly what I had which I wrote right at the beginning all right so I would say this is probably the most complicated code from a control flow standpoint that I've ever shown you this this algorithm is an in-place algorithm that does not require any extra storage and that's exactly why it's so popular people are sorting billions of elements in lists and you can't use gigabytes of storage during the sorting process right and what this clever strategy tells you is you don't need all of that storage you can do things in place and as long as you choose the pivot reasonably well you get your average case n log n complexity which is the same as the worst case complexity of merge sort so you have to be a little bit careful with that


As found on YouTube

Leave a Reply