Crust of Rust: Sorting Algorithms

hello folks welcome back it's been uh it's been quite a long time since since last stream um i did my thesis defense which is up on youtube i'll put it in one of these corners just like a little youtube card but apart from that i haven't done like a coding stream in quite some time and even this one so this will be a a crust of rust stream specifically so it'll be a shorter stream where we'll be talking about sorting algorithms and rust in particular we'll try to implement a few of them and the reason i wanted to do this specifically is because sorting algorithms are something that you come across in all sorts of languages uh people use them for coding interviews even though it's a terrible idea and you shouldn't do that um but but even just like in almost every cs education you learn about them in all sorts of language tutorials you learn about sorting because they're so common and like it's unclear whether they're useful like it's very unlikely you'll actually have to implement your own sorting algorithm for anything real that you build but the fact that they're so common means that they're a good comparison point between languages and so the purpose of this crust of rust stream isn't really to teach you sorting you can read up on these algorithms on your own instead the goal with this is to show you how these algorithms would be implemented in rust in a sort of idiomatic way so that you can compare that to languages you might be familiar with and then over the course of that my guess is that while implementing these algorithms we might end up sort of stumbling over a bunch of different interesting rust topics so unlike some of the previous streams where i've been focusing on a particular rust feature this one is more focused on on a broader set of problems for us to sort of code up and then see what we learned along the way as before here i'll sort of take questions as we go because it might be that there are things there are features of us that i use while we're doing this that you are curious about and want to see how work or why i did it that particular way i will say so i took a poll on twitter as to whether this should be the topic of the stream or whether i should do another uh stream topic which was specifically implementing an improvement to a concurrent data structure i maintain i'm going to do that one too that'll be a longer coding stream uh that will probably happen in a week or two i'm not quite sure yet all right so let's uh let's dive into this and and we can't really start the discussion before we talk about the ord trait so the or trait in rust is the way that you express types that be can be compared relative to one another now if you look at the or trait you'll see that ord requires that the type is eek so eek is sort of complete equality um and partial ord and partial lord is a partial ordering it says that the uh type is partially ordered and you see that partial ord is generic over the thing that it can be compared with um so for example you imagine that um some type can be compared to many other similar types so for example an uh a u16 can be compared to a u32 and and uh and so therefore there's a it is possible to order them relative to one another even though they are not the same type and that's what uh the the parameter to partial ord here is for ord you'll see that it actually requires that you implement partial ord of self and if you read the description of ord a little more you see that the requirement for word specifically is that the type forms a total order and you can see the exact definition here but basically the way to differentiate between ord and partial lord is a partial lord might say for for some two elements these do not have a relationship to one another like is the string 42 greater than or less than the number eight or the the string foo bar or the number eight are is one greater or less than the other it's it's unclear right they don't really have an order with ord you require that a given type must be comparable with itself of course but also you require that comparison to basically always have an answer to the question is is a greater than or less than or equal to b it can't just say it must always have an answer that's roughly what total order means um total order also requires that things are transitive but this is not a property we'll really avail ourselves of here the reason that we're using ord instead of partial ord for the purposes of sorting is because if we did partial ord it's really hard to order a thing if the order of some things in that set doesn't matter and so we're actually going to use ord this does have some weird properties because um there are certain types and rust that you might expect to be orderable but are not uh specifically the the floating point number types um those implement partial lord but not ored and the reason for this is that um floating point numbers also have this like um uh oh the name escapes me now but they have a special value uh nan not a number um which is used to express sort of floating point operations that don't have a well-defined answer uh and and those it if you have a nan and compare it to some other floating point number it's unclear how they're related to one another so uh f64 and f32 do not implement ord um yeah floats are also not uh eek for the same reason specifically that if you have two not a numbers they're not equal to one another which is weird um in um which is it's weird for two things that are equal to not compare equal but it's because not a number if you do one mathematical operation that gives nan and another mathematical operation that gives nan they're not necessarily the same nan that's why it works that way um okay so we're going to be relying on the ord trait um and if we scroll up here a bit and look for sort of sort methods you see that there are a bunch of um sorting mechanism mechanisms already implemented for you in rust the prime of these is if you have a slice you can call sort and requires that the t is ored and it just sorts the slice in place now you'll see here that it says the sort is stable if you're not familiar with with sorting algorithms a sort that's stable just means that if you have two elements in the list or in the in the slice that are equal it won't swap them while doing the sort this might seem like a property that's weird to care about um because you might think if if i have a list of numbers and two of them are eight why would i care whether it rearranges those eight or not um and it's true that for for sort of primitive types this rarely makes a difference but you can imagine you have some complex type that where you have two elements in the list that compare equal or but are not the same uh and you actually care about the ordering because say one happened before the other in some other sense but they are equal as far as sorting is concerned and you don't want them to be reordered um in general sorts that are you sometimes pay a little bit more for a sort that's stable because the sort doing algorithm is more constrained in what operations it can do you'll see that there's a sort unstable as well that does not have this guaranteed that it's stable and that allows it to either use less memory or or be faster so we'll look at that you'll see also that there's a note here about the current implementation and the current implementation is an iterative merge sort inspired by tim sort i don't know where that will necessarily be implementing the the rust sort function um like the specific implementation they have we might get to look at tim sort it sort of depends on how long the other things take i'm not sure yet you'll also see that there's a sort by so the idea here is that sort is if you have a slice of elements you just want to sort directly sort by is if you have a slice of elements where you want to sort them by um a custom comparison function so one example of this might be that you only want to sort them by a field of that struct rather than the full struct itself uh it might be that you want to do a reverse sort right you want to sort it backwards uh in which case you sort of want to do the the standard comparison between the elements but sort of flip the result um doing a reverse sort is is probably the most common use of sort by um there's also sort by key which is specifically for the case where you want to sort by a field or something like that where you just provide a function that maps from the type in the slice to some other type that is itself ord and then it sorts by that by whatever that that function returns ultimately uh we'll probably just implement sort because all these other ones are expressible in terms of what we implement with sort and what we're going to do is essentially define a sort trait and then we're going to implement that trait using a bunch of different sorting mechanisms and there are a lot of them so here's the wikipedia page on sorting algorithms and you'll see that like there are a lot of them and they have fairly different properties some of them are just straight up bad and but many of them there's sort of a trade-off between uh you see here whether they're stable how much memory they use their average complexity so this is um how many comparisons does it need to do for an for if you like took every possible slice if you will um how long would it take on average to sort it where n here is the length of that slice the best case is what is the fastest it can possibly run so it might be for example that for certain algorithms um if the slice is already sorted they do they just walk the list and check that it's sorted and then do no work so that would be the best case it's sort of the fastest it can run the best case input and the worst case is like um imagine that the slice was are was adverse seriously adversarially ordered before you called sort what is the longest the algorithm might take and of course you want an algorithm where the the worst case is as good as possible and well where all these values are as good as possible but ideally like the best case and the worst case are the same as the average case and the average case is low um and you'll see that in general it tends to be that the best you get to is uh n log n for for the average uh and there's some mathematical reasons why that sort of has to be the case but you see that some of them have a best case of n which is usually the fact that if they're if the slice is already sorted these algorithms do very little work um but you see the the worst case often gets quite badly right like n squared is a very large number uh whereas n log n is not that large um so i think what we're going to do is walk this sort of in terms of the order you tend to learn about these things um so we're going to start with everyone's favorite bubble sort and bubble sort is real stupid like it's not very good in terms of complexity its average performance is n squared which is not great but it is very very straightforward um and i'll show you why the other thing i want to do on the stream is sort of implement a very simple benchmark for these that just counts the number of comparisons that that each algorithm makes and then prints that out so it prints sort of the length of the input and how many comparisons each algorithm did for that input and then we should be able to very easily see just how much work uh how much more work one is than the other bubble sword is real stupid yeah it's true uh all right so let's do a cargo new i guess lib and we're gonna call it um what are we going to call this sorting library we're going to call it uh descending see it's going to sort an ascending order but descending is a funnier name bogo sword is pretty great swordify swordify is also very funny oh sort the letters and sort that's good i like that so that's uh what oh rst right yeah or that's great i love that it's sorted um all right here's what we're gonna do uh we're gonna mod uh bubble sort uh and we're gonna have a trait here that's gonna be just sort or i guess actually we're gonna have a trait sorter uh and the sorter uh is gonna be given a um i guess actually this is gonna be an instance method because the sorters themselves do not we don't expect them to have any state so sort is really just going to be given a a t and it's going to be given a mutable slice of tea where tea implements ord and i guess this is going to be the slice um and then what we can do is we can have a sort function if we want it to be really fancy right we have a like an extension trait on slice that lets them lets something sort using a sorter i think instead what we are going to do is just have a freestanding sort function that people can call and so this is going to take a t and an s and the slice is going to be a mu t where t is ord and s is a sorter and all it's really going to do is do s colon colon sort this is our public function and this is our sorting trait and then now all we have to do is implement the sorter trait for each of our algorithms uh and the we can just call sort on whatever we wanted and of course we could have here um this sort of what are we gonna call this like type actually let's go down here and write this as a test so we're going to have a struct standard sorter and we're going to implement sorter it's gonna be that's fine we're gonna implement a sorter for standard sorter ah i used to have a i forget what the implementation of this was coc command no clc action oh that's too bad i used to have it set up so that i could just like press a hotkey for automatically adding the methods for the trait but i forget what the hotkey is and i don't want to look it up because it takes too long um how much harder would it be to implement these for iterate or mute um it's actually much harder to do it for itter because you don't know how many elements you're gonna get like realistically it's really hard to s it's fairly hard to sort a stream it significantly limits what algorithms you can use uh unless you collect the stream into a vector and then you sort the vector right so it's unclear that buys you very much and this is why in the standard library two you generally see sort on on slice um and all this is really gonna do is just call slice.sort right uh i guess here we have to use super right so we're ever going to have a test here that checks that i guess we're gonna have like things is gonna be a vac of [Music] four two three one and then we're going to call things dot actually we're going to call sort of mute things uh and we're going to do that with the standard sorter and then we're going to assert that things is now equal to one two three four this is sort of a sanity check that the the setup we have is roughly right um so let's cd into horst and run cargo test oh right i don't have bubble sort yet so let's comment that out uh how's the font size do you want it to be smaller uh yeah random access is also very useful in sorting you basically need that so you could use exact size iterator you would then know how many many elements to expect but ultimately you would need to have all of them before you could really start sorting them in a reasonable way um right the challenge is that the later elements might end up shuffling a bunch of things around you'd basically be forced to do uh sort of something like an insertion sword uh which is pretty bad a bit smaller all right let's do that better let's do that all right uh so that works for us so now let's go and implement bubble sort actually let's do do we want to call it bubble sort or just bubble let's do bubble sort that's fine uh so we want to use super sorter and we want a sort of pub struct bubble sort and notice that these are all these are all just unit structs because the sorter itself doesn't have any state you could imagine that the sorter had like configuration that was stored in it but it doesn't really have state um why does vim say object object in the status bar i'm not sure it might be that i have the my rust analyzers outdated or something it definitely normally doesn't do that i also don't know why it says like a heart rust analyzer i think like something in my setup is broken but who knows why um all right so we're gonna implement sorter for bubble sort and let me just copy that method from over here and so this is the thing that we have to implement right and so the question is what goes here my chat window is like no longer auto scrolling which is pretty annoying um i have coc set to uh stan um manually compiled russ analyzer because i want to run it on like the latest nightly um okay so bubble sort bubble sort is a real stupid sort where all it really does is um it just walks the array and swaps anything that's out of order uh you may be familiar with this already so what we're gonna do is sort of we're just going to have a loop we're going to set swapped equals false at the top of the loop then we're going to walk all the elements of the slice and this is just going to be 0 to slice.len and if slice i is greater than slice j uh then we're gonna just do uh slice dot swap i and j and set swap equals true and in fact we can do this while swapped swapped equals false all right so this is why people love bubble sort um it's not quite correct yet it has some boundary problems that we're gonna have to fix um but bubble sort is really really um just it's really straightforward to implement um oh man why is this there we go um so all we're gonna do with bubble sort is just walk the slice and anytime we see something be out of order we're going to swap them we're going to keep doing this until we've walked the whole thing and we never had to swap anything right very straightforward but also super slow you'll notice that there's a there's one challenge here which is that i plus 1 might be out of range and the way we deal with this is just if i is slice dot len minus one uh then we continue and the reason uh the reason for this is because we when you're looking at the last element there's nothing for you to compare it with and it's already become compared with this predecessor because that was when we were at i minus one which actually means so we can just do this um same thing and now this will always be in range right so uh isn't this going to stop on the first swap uh no so while we we continue while we have swapped something right um and we keep setting swap to true whenever we do do a swap and so we're going to keep looping until we have walked the whole thing without setting swap to true at which point the while we'll end i mean we can check this right so um down here we can have a little test it works uh and this will use the bubble sort uh super sore and in theory if we run cargo test now great bubble sort sorts uh we can even if we wanted to make this sort of be an odd length and see that it still sorts why is my chat not auto scrolling this is really awkward uh don't quite understand what's going on there let's hope it just fixes itself um oh yeah you're right we if we wanted to we could do uh one to slice len and then do like i minus one to i uh this has the same effect and it's maybe shorter un unclear that uh unclear that it's nice the youtube stream delay is real slow um so slice swap is sort of the the thing that's kind of interesting here it means you don't have to like read out one and then set the other and then set the other back like you don't need a temp variable and i think internally it does use memswap um right so why does this require the underscore um this requires the underscore because uh we have two type parameters to this function one is the type of the thing we want to sort and the other is the sorting algorithm the only thing we could really do here is we could make these be reversed uh the problem is that here because we're trying to name the we're trying to nape the sorting type here um rust won't let you if you're gonna name the generic parameters you have to enumerate all of them you can give underscore for the ones that you don't want to name and have it be um inferred by the type system but you do have to put placeholders for it um oh this is extremely annoying let's see if this helps um okay so we have bubble sort let's move on to the next sort let's go back here so we did bubble sort uh bubble sort is really bad but it works pretty well um and in in the sense that the implementation is very straightforward um our next contender this then is insertion sort um insertion sort is also as it says it is much less efficient on large lists than more advanced algorithms but it has a simple implementation love that all right so what is the algorithm for insertion sort well insertion sort is i won't make you read all of this uh but it might be easier to show in code insertion sort insertion sort and let's just copy all this in here so insertion sort is also fairly straightforward um the strategy we're going to take here is that we are going to sort of keep we're going to divide the slice into sorted and not sorted where the sorted part is sorted and the not sorted is not sorted and sorted is initially empty not sorted essentially the entire list um and then we're going to do is we're going to take one element from not sorted and we're going to place it in the correct place in the sorted list and then we're going to do that until there are no more not sorted left uh why not sorter sort directly without the freestanding function um we could do that uh so we could do like insertion sort uh sort uh mute things this also works and is sort of nicer the downside of this one is that you need to have the sorter trait in scope so this will only work if you have a use sorter sorter i believe but you're right it is it is a lot um nicer ah that's fine it obviously doesn't sort yet but um you're right this is much nicer let's do that instead and i guess we'll do it in lib2 uh the s not being capitalized yeah fine we can do that uh i guess let's do that for bubble sort as well all right you happy now um it can't be partial eek because partially it doesn't let you order things uh and it can't be partial ord because as i mentioned in the beginning you can't really order a slice if some elements just say i don't know what the order should be here and it's sort of unpredictable which ones right sort doesn't look like a word already i know right um okay so you iterate over search result in bim with the n key so what we're going to do is sort of have a some some threshold i uh let's say that is unsorted and unsorted is initially going to be zero so the idea is that everything beyond unsorted is going to be unsorted and everything before unsorted is going to be well sorted and in fact what we can do is we can immediately start this as one right because a list of one element is always sorted we don't have to sort that first element so what we're now going to do is we're going to walk all the elements we're going to say for unsorted in one two sorted dot len so i actually need to keep this as a variable because the iterator variable oops uh slice dot line because the iterator variable can can keep track of where that index is already and at this point uh slice unsorted and onward is unsorted is not sorted uh take slice unsorted and place in uh sorted location in slice up to unsorted does that roughly make sense what we're planning to do here um and this is a little weird right because imagine that that um you have like uh let's say that it looks something like this right so we have one two three because everything before they're sorted uh and then one three four and then the last element is two right so now we're going to pick up the two and we're going to place it in sorted in the right place so the two needs to go here that means that everything else has to be shifted over so there are a couple of ways you can do this the easiest way to do this is just to keep moving the element you just took left until the next element is smaller right so what we do here is uh we end up removing the barrier right because we're moving the element into the into the sorted side so it's going to go over here uh i guess let's indicate that this way and then we're just going to keep swapping it oops too we're going to keep swapping it to the left until the next element is smaller than the current element uh right so while uh slice uh i is unsorted while slice i minus one is greater than uh i and again you'll you'll recall this i um while i is greater than zero and that and uh should say slice right so we're just gonna keep shifting it left uh until it no longer needs to go left that just sounds like bubble sword going through an identity crisis so it's not quite right so bubble sort is even worse than this because bubble sword walks the array and it just swaps things that are out of order each time whereas the insertion sword doesn't really swap everything it doesn't walk the whole thing right it walks backwards from the thing that you're now placing um and so it it only does the swaps that it sort of needs to do um and okay so you might wonder uh okay so some people are saying like isn't this more of a bubble sort than an insertion sword um it's it does have a little bit of the semblance of a of a bubble sort but what this is really doing is doing the shifting at the same time oh yeah you're right uh i'm i minus equals one um so imagine that we just picked up this two and try to place it here what we would have to do is shift the remaining elements all over by one right um and i mean okay there's a there's an alternative way to do this right which is to walk the array until you find the location that you need to put it in uh and then like mem copy all the things from that position forward one over and that would also work it's a non-overlapping mem copy so it's not that efficient anyway because ultimately what it ends up doing here let me see if i can draw this actually here oh yeah insertion sort works a lot better if you're someone mentioned this in chat too if the storage mechanism you have if it's not a slice but if it's a linked list then insertion sort is great because you don't need to do all this shifting over you just find where it goes and you stick it there you just like if you have a linked list right you just pull them apart and stick it in the middle the problem with the slice is that you need to move all the things over so let me try to draw this out so we have this list and it has a bunch of elements it has one three four two let's say five right and it's sorted up to this point and so now we're trying to move this barrier over to here right so what we're going to do is we're going to pick up we're going to pick up the 2 and we realize that we have to move it to here now there are two ways to go about this right one is to go over here right um like so one is to walk the list left to right until we find the slot where it has to go into right so it's like oh it has to go here and then sort of store two somewhere to the side and then take these elements and shift them all right by one right so that's going to turn into this goes here and this goes here so that's one swap to swap the other is what we currently implemented which is swap this left then swap it left again so they both end up being two swaps um and the the biggest difference between these is that this one walks from the left and looks at each element to the sort of left of the target location whereas our swap goes from the right um it's you don't know in advance whether walking from the left or the right is going to be more efficient because you don't know where this element is going to go they're going to have slightly different runtime characteristics based on the data but in terms of complexity they're the same would it be cheating to use binary search plus insert uh yeah i mean we could totally do that it is true that uh you can be more you can be a little bit more efficient here with a binary insert to reduce the number of comparisons you have to do it still has to swap all the elements right so um what's being proposed here is that like let's do like if not smart then do this else do this smart equals false alright so this one is going to use use binary search to find index then use dot insert to splice in i so here what we have to do is do slice dot binary search so binary search is a method that's provided by the standard library on slices which gives you a type and a type that implements ored and it's going to tell you where that item should go oh my hair is being weird today so if we do a slice dot binary search for slice of unsorted this is going to give either an eye or an eye let me explain why these are different in a second and this is going to tell you where that value should go in slice assuming the slice is sorted and it's going to use binary search to get there so a binary search if you're not familiar with it is like you look at the you look at the if you have a slice is this long you look at the element in the middle and if the thing you're comparing is larger than the thing in the middle then you now look at the middle of the second half if it's smaller you look at the middle of the first half that way you do log n comparisons rather than n comparisons um in terms of trying to find that location and then we use slice dot insert so um if we pull back here for a second uh this might give me really unhelpful um oh that's only implemented on vec uh i think slice has a splice method uh no i think there's a splice so the reason why maybe there isn't well that's awkward yeah um so the reason why there's so there's an insert method on vector and what it does is it it does all this shifting for you so you say like i want this element to go in position three and then everything beyond position three gets pushed over in the implementation by using some like smarter mechanism than just swapping um the reason why this is only implemented on vector is imagine that you told it i want to stick this element here and pushing all of the remaining elements out ended up you ended up exceeding the capacity of the vector then it might have to reallocate right allocate more memory so that those elements can fit in this case we know that that's not case we we wanted to overwrite the element like we wanted to sort of drop off the element that shifts um to the right because we know that that is the element that we've picked up and are inserting um but slice doesn't have a method like that so we would have to do all the swaps anyway um so here we would do like uh well i don't even know that i want to write this code but it basically would do this sort of swap loop except they wouldn't have to do the comparison uh it would only have to do the um the actual swaps uh you're right this should be dot dot unsorted um so for that reason i think we're gonna just ignore the smart implementation for now um it's true that it would be it would use um uh log n well n log n uh it would be n log n instead of n squared um which would be good but you still end up with n squared swaps uh so like it's still pretty costly like this is not the way to get better sorting it's not to optimize uh uh insertion sort oh there's a rotate right ooh okay so rotate right might work uh slice rotate right oh that's pretty good in fact then we can do even better uh so let's use rotate right so rotate right shifts all the elements in the slice over by one but with a wrap around and this you can do without resizing because you're going to wrap them around right so we're going to slice everything over by one but here what we can do is actually be a little sneaky we can say we want to rotate everything right starting from the target location and ending at the element that we're moving and what that's going to do is it's going to shift all the elements that uh that are before the element we want to put at the beginning or put at the the eye we found over that's going to cause the last element which is the one that is currently unsorted to go to the front which is the position that we wanted to end up in always rotate right only on nightly that's interesting no it's not a nightly great so we can use it um okay so that brings us to why does binary search return okay and error um it returns okay so okay so imagine that you're you have a list like um uh one three five right and then you do binary search for two well let's do let's do three first and you do binary search for three this is going to return one right because the three is at the one at index one right i guess let's make these a b c it might be easier or a b c is bad a c b and we're gonna search for c that's gonna return one but you can also search for elements that aren't there so if i search for b this is actually going to return a this is going to return error of zero let me just double check that i'm not lying to you sorry error of one uh so this value is the if you get an error it's i didn't find an element that matched but if you were to insert this element this is the index at which it should be right so in this first case it's we found an element that has the exact same value in which case we can put it before or after it doesn't matter because it's equal this would matter in terms of whether it's stable but it wouldn't matter for the purpose of leaving the array sorted for the error cases saying this is where it should be like all the preceding elements are smaller and all the succeeding elements including the one i just gave you are larger and so those are all the ones we're going to shift over um so let's let's see if this works let's do a test run okay so with smart equals false what about with smart equals true great so both the smart and non-smart version works so this is where we can actually have values on this right so we can say smart it's going to be a bool although that would mean that sort has to take so we actually need to change our sorting implementation a little bit here we need to say that the trait takes a reference to self which means that let's have this just go away this is going to take a self and just not use that parameter this is gonna do that and for bubble sort uh this isn't gonna make a difference because we don't really have a configuration for it it takes a self parameter but it doesn't use it and this becomes bubble sort so the the change here from a double colon to a dot is that previously it was you can think of it as like a class method from other languages but it used to be um an associated method of this type whereas now it is a method of the type so now actually we're constructing a bubble sort value and then we're calling the sort method on that value and these are different uh what happens if you binary search on an unsorted slice you basically get a random index it's not quite random but but essentially and now for insertion sort what is nice about this is that we get a self and so now down here we can say if not smart and if smart some people are asking whether there's a better way to write this match i don't think there's an easy way to like unwrap the unwrap both and assume they're the same type you could probably do you could do this with unwrap or else so you could do unwrap or else i i this will do the same thing but but i like the fact that this actually documents what the two branches are so you don't actually need to use a match here right like uh let me write it down here might be cleaner than trying to see it all the way to the far right uh unwrapped or else i i uh it's the same thing but but i i prefer this version because it's more explicit in terms of like how it performs is probably about the same um all right so now we have insertion sort we have an error somewhere right this has to be dot smart is true it works dumb and it works smart great um isn't the static function when you don't need an instance of the object to call that method yeah so you can think of it as a static method in the future you'll also be able to do this with or let patterns which i think someone mentioned in chat too so you'll be able to write soon and i'm very excited for this is you'll be able to write this whatever like slice unsorted etc um and the same and it basically lets you do so you can already or patterns right so you could write this as this you can already have or patterns in in match statements but you'll be able to do it in um in let statements too which is really neat um oh the phd mug yeah my girlfriend got me this after when i graduated so it says uh dr jengset on one side oh maybe you can't see it and then it says uh done on the other side it's great um all right insertion sort let's move on to selection sort and actually this time let's copy insertion sort to selection sort and insertion to selection all right so selection sort i guess let's go back to the wikipedias um a selection sort is also n squared so it's inefficient it's generally worse than insertion sort but it is very simple one thing that is nice about selection sort is that you can do it like entirely in place you don't need to use any additional memory um and when i say additional memory what i mean here is that behind the scenes when you're doing this like swapping you often have to like store something to a temporary variable and in general that just like doesn't matter like you have to store something of size t in addition and you store it on the stack but there's some cases where you're so memory constrained that you just can't store extra elements and with selection sort you don't actually have to do that so the idea behind the idea behind selection sort is that we're actually just gonna walk we're gonna uh we're gonna pick this you're gonna find the smallest element of the list and we're gonna stick at the front then we're gonna find the smallest element in the remainder of the list and we're going to stick it at the front and we're going to find the smallest element of the remainder of the list we're going to stick another front and then at the end you've now sorted the array right so obviously this is super slow um but it doesn't use any extra memory and it's fairly simple uh so let's look at what this looks like uh so we're gonna do for unsorted in one to slice and just like with insertion sort we're going to keep the prefix sorted and the suffix is not sorted but here uh the implementation we're going to have is going to be a little different uh selection sort does not have any arguments it is in some sense always dumb um obviously these tests are bad like this should be like prop test or something because this is entirely stupid uh this only tests a particular case whereas with something a prop test or quick check or something you could actually have it generate like arbitrary vectors to make sure that they all end up sorted um you can you can also swap with xor as chat is pointing out but for for something like the rotate right you can't necessarily or it gets really convoluted if you wanted to do with just xors uh so usually you end up using temporaries uh all right so so our plan our plan here is gonna be um smallest in rest is gonna be the sort of if we really wanted to cheat here right we do uh slice unsorted to the end uh min uh and this is gonna be yup and then we're gonna slice dot swap unsorted with smallest in rest uh this i guess this should not be min but like the min eye all right fine we'll we'll do this the the slow way um so smallest and rest is going to be we're going to assume that it's the current element and then we're going to walk the uh the rest of the list for i in unsorted to slice.land [Music] technically this is going to be plus one and if slice i is less than smallest in rest then the smallest and rest is going to be i and if unsorted not equal to smallest and rest then we're going to swap them huh that's [Music] nice yeah so this what we're doing here we can start from one we don't have to start from zero because the uh slice of length one is always sorted um oh you're right it's not it has to be the smallest element you're completely right this is different from insertion sort in that we're going to be moving we're not going to be moving elements to the appropriate place in the slice we're going to assume that it always is the largest of the sorted so think of it this way the smallest in the remainder is going to be the largest of the thing that's sorted and therefore we need to make sure that the first element is the smallest of the whole slice and that's why we can't just assume that the first one is already sorted and so here what we really do is we just walk the whole list and continuously check for the smallest element in the the remainder and shift that to the beginning of the remainder and then we keep shrinking the remainder uh what i was looking for earlier is um there i think there is a uh let's see unsorted so there's a there is um i think this rust analyzer is giving me the wrong thing here um i guess not i was pretty sure there was a min but i guess not oh it's on iterator yeah so slice is an iterator right so you can call dot min and that gives you an option smallest element the reason it's an option is because the slice might be empty but this gives you the smallest value not the smallest index now we could in theory do this with some like a little bit of magic wrapping by using the enumerate function on iterator so i might as well show that too so a sort of different way let's do or is to do dot itter dot enumerate dot min by key uh dot unwrap or i guess expect uh slice is non-empty so this is smallest smallest in rest uh actually this is going to be the i and the value and we're going to have smallest and recipe the index right i'll explain this code in a second uh no that's almost certainly a lie why is that failing uh lifetime may not live long enough that is very interesting indeed wait i need to see this error properly from cargo oh that's why um okay so what we're doing here is and the annotations from rust analyzer are actually going to be a little bit helpful here so we take the remainder of the slice write everything from unsorted and onwards we create an iterator over it we call a numerate which is a method on iterator that changes the iterator from b just over the value to being an iterator over the index and the value so a tuple of index and value and then we call min by key which gives us the smallest it walks the entire iterator and it gives you the smallest element according to whichever value you get from calling the provided closure on each element and in this case what the closure does is it fishes out just the value right because every value in the iterator after enumerate is a tuple of the index and the value and we only want to find the minimum by the value we don't want to find the minimum by the index for example and so we fish out just the value and this technically gives us an option back because well it's um it it has to because the iterator might be empty but we know that it's not empty so we can expect um and the the lifetime issue i was seeing was because min by key gives you a reference to each element and the reason it gives you a reference rather than the element itself is because min by key is going to walk all the elements and then return one to you so it can't give ownership into this closure but v is also a reference itself and it's a reference into slice and the reference to the tuple only lives for the duration of the iteration because it's an uh reference to a value that was yielded by the iterator uh and but what we're trying to return is a reference into slice right and after the iterator returns the iterator values which is what this reference is the iterator values no longer lives so we can't return it and that's what the compiler was complaining about so what i'm doing here is i'm telling the closure to de-reference the tuple and then fetch out the v as opposed to giving a reference to the second element of the tuple uh this might be easier to show if i just said min by key gets a t and previously what we're doing were was uh the way i was writing it right i wrote it as just this and the compiler was complaining right this was an error um because what i what that is equivalent to doing is this right so that gives that same error um so this is clearly a reference to the tuple itself it's not a reference into slice it's a reference to a reference and by rewriting it to be this what i'm really saying is this uh uh think of it as a an ampersand in a pattern is the same as a removal of an ampersand in the value um is one way to think about it um and smallest in rest here is also going to be an index into this slice which starts it unsorted so we actually need to adjust it slightly to be unsorted plus smallest in rest uh and then what we can do here is just for the sake of our own sanity is like assert equal smallest in rest and smallest in rest two and let's see what that does great so that works so the question now is do we prefer this very explicit way or do we prefer sort of the the functional iterator way in terms of performance i think they're going to be likely the same the compiler is pretty good about optimizing iterators but it's also pretty good about optimizing um for loops for loops are iteration iterations rust so i think what we're going to do is keep the iterator version because it's a little nicer and i think it's not cheating to rely on min by key because in order to implement sorting because mean by key is not a sword uh remember that this one was mostly some people are saying like i prefer the the second version the second version is very straightforward in terms of just like you can really see what it's doing this one is very much there it's much more readable it's just this part is a little wonky but if you read it your brain is going to ignore this part right and just be like yeah it probably does what i expect so i think we're going to keep it this way and in fact if what we could do here if we really wanted to was map the i and the value to be unsorted plus i uh and then this can be this and this can be this uh it's a map here because it's um it's an option before we expect out all right okay so we have now selection sort beautiful so bubble sort insertion sort selection sort and standard light resort great so far these have been like fairly straightforward sorting mechanisms and so now we're gonna start to look at the ones that are not quite as stupid so if we switch back here uh the next one and probably one many people have heard about is quicksort which is its own kind of cool um does the compiler take advantage of assert statements uh no well actually no i think it does um because the assert turns into a uh a conditional with an exit on the branch where the conditional doesn't hold so the compiler can assume that the conditional holds in the following code how much it takes advantage of this i'm not sure all right so we're gonna do a quick sort uh this is we're gonna base this on selection sort i guess all right so quicksort is uh quicksort is more of sort of a beast than the others because it's not it's not quite as straightforward but it's not that complicated um so the way quicksort works is you pick um you pick an element basically at random in the list and then you walk the list and you put everything that is smaller than that element to one side and everything that's larger that element to the other side and then you just continue to do this sort of recursively down until all of them are sorted so for quick sort it might be might be helpful to write a little helper method and we'll get to that in a second so the idea is that you have like unsorted you have a pivot and you have an unsorted and the pivot can be chosen randomly uh it can be it can be the first element it could be the last element it could be the middle element uh there's actually been some research on like how do you best choose the pivot uh and you can get some pretty good improvements by choosing a good pivot in this case i think we're just going to choose sort of randomly and so the way we're going to do this is i'm going to write this in an allocating way first and then we can look at having it do be in place instead but the allocating version is going to be easier to understand so we're going to do that first so what we're going to do is we're going to have we're actually going to call quicksort we're going to have a function called quicksort and we're going to call that on slice on the whole slice and you'll see why in a second basically this needs to be recursive so a quick sort takes a t that's ored it takes a slice of mu t and here's what it's gonna do uh let's do like this um it's gonna select a pivot which is gonna be slice let's do zero seems fine oh actually i realized uh i think someone pointed this out and i was just too foolish to realize uh selection sort oh no it won't matter i was thinking i was uh maybe it'll be here no i just realized the list were asked to sort could be empty but i think all of these will deal correctly with that case um okay so we're going to pick a pivot and then we're going to have like uh let's call them left and right uh and then we're gonna do is we're gonna walk uh walk all the elements of slice and uh if slice of i is less than or equal to the pivot then left dot push slice i else right dot push slice i right so all the things that are smaller than or equal to the pivot are going to go in the left and all the things that are greater than the pivot are going to go in the right and then we're going to quick sort left and then we're going to quick sort right and then we're sort of going to merge them together now this is technically all you need for a quick sort right um uh there's no difference between t colon ord and where t equals ord or t color nord um so this is all quicksort really does and it you'll notice that it's recursive uh and the recursive part here is what makes it interesting we're gonna left and right are gonna keep shrinking right they're gonna become smaller and smaller and smaller um and at some point they'll only be one element long at which point they're sorted uh so we can actually do here uh if slice dot actually we can even match on it match slice.len if it's one then we return because the slice is already sorted if it's two then uh if slice zero is greater than slice one then swap zero and one and then return otherwise do this bit all right so this is sort of the the base case for the recursion that at some point you end up with a list that's so small that it's trivial to sort uh and then you just sort of propagate it back up uh and then we're gonna merge the two lists now you'll notice that this is actually really inefficient right because we have to allocate this left and we have to allocate right and then we have to do this like merge step and this all seems really annoying um and you'll also notice it doesn't compile and the reason is because we keep trying to move these elements around which isn't really okay um uh oh right we also need a zero so zero or one um right we're trying to move out of the slice but we're not allowed to move out of slice so we would have to do some like tricks to either move the references or like have or have left and right only hold indices and this gets really annoying um but at least now you have an idea for like at a high level what does the algorithm do so what we're going to do is we're actually going to implement quick sort as a as a an in-place sort so we don't need the a vector for left and a vector for right instead what we can do is um is just have left and right be the left side and the right side of the slice and we keep growing them from the sides so let's see what that looks like we still need to pick a pivot uh for now i'm gonna this is still not gonna compile eventually uh but we'll we'll get to that so here's what we're gonna do um actually i have an idea but i'm going to ignore that for now um here's where we're going to 4i in 0 to slice dot land in fact we can have this be from 1 and the reason we can have this be from one is that the pivot if the pivot always goes to the left we don't need to move it and in fact this is going to be one of the ways in which we avoid the borrow checker errors here is we're going to do is it partition at index let me check whether that's the case uh no that's not what i want i want a split split mute no i want maybe to split at split at mute great split at mute of one so what this is gonna do is pivot equals uh pivot zero so we're essentially sort of stealing the first element out of the slice uh and what splitted mute lets us do is get a mutable reference to the two sub slices where one sub slice is going to be one element long and hold the pivot and one um sub slide is going to be the rest of the thing that we're actually going to sort and keep in mind right that the pivot is already in the correct end of the the slice we're going to instead of having a left vector and a right vector we're going to have the left side of the slice be things that are less than or equal to the pivot and the right side of the slice be the things that are greater than the pivot well then the pivot is already on the right side yeah we will we will write benchmarks in a second okay so now we have a reference to the pivot but we're still allowed to modify the slice right and this is important because if we took a an immutable reference to the pivot um then we wouldn't be able to modify the slice if we didn't do the split at mute business because the borrow checker would complain that you already have a reference into the slice so you can't also modify it because if you also modify it who's to say that you're not also modifying the pivot value which you have a reference to right it's on the right side the left side oh maybe my camera is reversed might very well be um okay that's not at all what i wanted to do uh okay so now what we're going to do is we're going to walk the slice uh and you're going to see in a second this this for loop is actually going to change uh in a bit but i'll show you why um and what we're gonna do is uh again if slice of i is less than equal to the pivot then what we want it to do is then we just want it to stay in place already on the correct side so this indicates that we need some like left side and some right side indicator um then since we're walking this from left to right um if the next element is or is less than or equal to the pivot then it's already on the left side and we don't need to do anything with it otherwise we're going to have to move element to the right side right because it's on the wrong side this gets really complicated because now the current element we're looking at needs to go over to the other side but that means we have to do a swap and at that after the swap we have to continue looking at this side right which gets weird so the for loop won't really serve as well here because the for loop would just move on to the next element but we given that we did a swap we actually need to look at this element again so what we're going to split first mute ooh nice i did not know there was a split first mute nice slice is not empty that is indeed much nicer oh it's using slice pattern matching that's cool yeah we could have done that here too um so what we're going to do instead instead of having this for iron slice is we're going to have a while loop and for now let's just make it be a loop and we're going to do is we're going to look at the uh think of it as everything below the left index is on the left side everything above the right index is on the right side right so what we're going to do is we're just going to continuously look at the element that's on the left and see whether it needs to go on the other side so if slice left is less than or equal to the pivot then it's already on the right on the correct side and we don't need to move it otherwise we need to move this element to the right side well now that this is no longer a for loop let me just tidy up this a little bit uh now that this is no longer a for loop this becomes a lot easier what we can do is we can do a slice swap of the left with the right and then we do write minus equals one does that make sense so think of this from a useful way to think about especially these kind of iterative uh methods is just like walk through what actually happens so imagine that we have a slice uh and we've we've already extracted our pivot so this imagine that we just have a pivot somewhere and we have the remainder of the slice left is zero and right is the end of the slice okay we look at the i guess i don't know which side is left for you ah let me draw instead all right so um we have our pivot over here right and then we have the remainder of the slice [Music] i drew this last far too long so we're going to keep is we're going to have a left and we're going to have our right um and think of write as pointing to the end of an element and left is pointing to the left the start of an element and so initially left is empty because it's all the elements before left and right is empty because it's all the elements after right so maybe it's more useful to think of these as like pointing to the middle but it doesn't really matter right does everything after the element not including the element itself is left and left is everything left of the element not including the element itself um and now the the iterator code right is going to look at the element at left so this element is not in left but it's at left so it's going to look at this element and if that element is less than or equal to the pivot then it should be in left so all we're going to do is we're going to like move left let me say color this color is the next iteration color now left is going to point here right and everything to the left of where left points is in left so the pink one is now in left and everything to the right of right is in right and there are no elements to the right of right so right is empty so now it looks at this element and imagine that this element is not less than or equal to the pivot so that value needs to go into right well what we're going to do is we're going to swap this element with that element whatever element is over here right uh and then we're going to shift we're going to decrement right so right is now going to point to here right and blue is going to end up over here and at this point some other element let's say green is going to be here instead of blue right and now again everything to the right of right is in right so blue is now in right as it should be and now we continue to look at where left is pointing left is still pointing here so now we look at green which is the one that used to be at the end and if green is less than or equal to the pivot and then we keep going so the question now becomes what's the termination condition here right right to the right of right right yeah exactly um blue and green kind of looks the same yeah sorry about that hopefully it was clear from the explanation picking colors on the fly is hard i should really just set up like a good palette but so the question becomes when do we terminate well we terminate when left becomes the same as right so at some point there is no more elements to there are no more elements to look at this might not be true this might be enough by one um again when doing these kind of thinking it's useful to think about the boundary conditions like what happens at the beginning and the end so let's say that we have just a two element list left points here right points here uh we look at this element we shift left over this is in left these are now equal but we have not looked at this element yet so it might be in left or it might be in right so this is not the termination condition we need to do one more iteration so them being equal does not mean that you should exit you should exit after they were just equal uh so um this should actually be while left is less than or equal to right the moment left becomes more than right then we're done uh we don't need to leave a hole for the pivot the pivot is already on the correct side uh okay uh and this is probably complaining that we're trying to compare immutable reference to uh there we go so slice left gives you a a t uh and you're trying to compare a t to a mutable reference to a t uh we need to compare by reference um okay so now we have an in place sort of pivoting notice that this on its own is not sufficient right that's just gonna like split the thing into things that are smaller than the pivot and things that are larger than the pivot um i am not swapping beyond the length of the slice right is slice.n minus one so no i think that's i think it's currently correct um this does not actually sort right all it does is it moves all the things less than the pivot to the left and all the things that are greater than the pivot to the right but but those things are not themselves sorted so we still need to do a quick sort of the left and the right um so how is this going to work well we basically need to recurse what's nice here is we don't have to do the merge step because the merge is sort of gonna happen on its own because we're essentially sorting the sub slices in place what this means is that there is no merge step to do when all the recursion finishes the the whole array is sorted so the only question becomes how do we know what to um what to pass into quicksort here one tricky part here is this slice business should really be rest because we need to refer to the slice down here oops it should say rest and this should say rest and now what we're going to do is we're going to quick sort uh let left and right is going to be the splice and we're going to split it and the question becomes where are we going to split it well we know that everything that is less than anything before left is in left right and everything that's after right is in right and split at mute so split at mute takes a mid i think they call it oops not mit and it gives you two slices one is a mute of um everything up to but not including mid and the other is uh mutable to everything from mid and onwards um and so this is going to be left right so if we provide left here that's going to be everything up to but not including left which is indeed what is in left and everything else is in right and i misspelled right could you add an extra fels branch to just move the right counter without a spot swap if it's already on the right side uh yeah so there's one cool extra step we can do here right which is if the thing on the right is greater than the pivot then we can just decrement pivot decrement the right avoid unnecessary swaps back and forth so the reason why this extra class is useful is imagine that um i guess let's go back to the drawing um how am i gonna demonstrate this um so let's imagine we have a very small slice here so it has just like let's put some numbers in here let's just say it's one three five um so initially left points here right points here um uh that's not i need an extra number in here that's annoying uh i think i even need an extra box so let's make this be four boxes um let's say this is one four two five so left points here right points here um so initially we're gonna find that one is in the correct location so we're gonna move this to point here right so this is left this is left this is right then we're going to look at the 4 and say well 4 has to go in right so we're going to go ahead and swap these two right and so what we're the position we're now in is 1 5 2 4 with left pointing here and right pointing here but this was sort of a useless swap because the next thing we're going to do is swap 5 back into right so 5 now got swapped twice even though it was already on the right side and this extra if clause avoids us having to do that it basically tries to it tries to move left and right without having to do swaps until that's no longer possible so that's a little bit better why are we splitting again if we already sorted rest we haven't sorted rest we've just sort of i mean it is we've just sort of uh done like a binary partition it's not fully sorted uh instead of while less than or equal to uh a loop and if left equals right break no i don't think you could use an if left equals right break because you want to break after processing the case where left was equal to right i mean you could it would just be a it wouldn't really be that nice um oh yeah you're right actually we can also do left plus equals one so uh left holds a right and right holds the left swap them so we actually make progress on both sides when we do that swap but it just saves us one iteration really um great um yeah so so once we've done that sort of partitioning then we look at the two partitions and we recursively call quick sort now there are variants of quick sort where um if you if like the the slice you end up with is sufficiently small like smaller than three or something then you do like a selection sort or insertion sort or something because those are efficient at if you have small lists that way you don't have because this the actual this part of quick sort is kind of slow and so if you have a small enough list you can use another sorting algorithm but i think we're just going to leave it the way it currently is even this two clause is unnecessary um all right so let's see whether that does the right thing it does not great uh initialize left equals one uh so left remember is an index into rest it is not an index into slice oh actually that's where this is currently wrong um it needs to split at left plus one the pivot right so left left is an index into rest it's not an index into slice uh and rest is slice plus starts at slice plus one because of the pivot uh so we do need to add one to that oh quicksort has overflowed its stack that seems not great um that suggests that these are not shrinking oh yeah um yeah the problem we're running into here is that okay so basically what this means is infinite recursion um which i think happens because we're always choosing the pivot to be the same element and it might be that the pivot is the largest element in which case everything will always end up in left so left will never shrink and therefore we just keep um we just keep growing we keep calling quicksort on like the entire slice and it never gets any smaller because right is always empty so what we need to do well there are a couple of ways to do this one is to pick the pivot randomly i think realistically what we need is um we need to make sure that the pivot is not the max value no we just need to make sure that the pivot does not go in the same problem is it we can't just put the pivot in the right either because if we put the pivot in the right you have the same problem if the pivot is chosen as the smallest element i think the problem running into actually is that we don't move the pivot so the pivot the same pivot ends up being used over and over again um the way we can get around this i think actually let's see what the page says for quick sort for choosing the pivot um equal values can go either way uh after this partitioning the pivot is in its final position i see it should not include the pivot why is that i see so the the real algorithm actually does exclude the pivot hmm typically that's the last element the array that's interesting hmm yeah you don't have the pivot in either of them um oh right it's um i i know i know why uh okay so the pivot is supposed to end up in the the final sorted place in the array but the way we've done it is that we chose the pivot to be the first element and then we didn't move the pivot at the end so the pivot is still included in both the sub slices so one way that we can do this is place the pivot at its final location explicitly and the final location for the pivot is to place it after all the things in left and before all the things in write because that's how we partitioned this in the first place right so the way we do this is just we do one last swap which swaps um zero which is the pivot with uh with i want to i want to say left minus one right so it it swaps it with the last element in left so the last element in left right so everything to the left of left is in left so the last element of left is swapped with a pivot and now we have the pivot placed so that everything that is less than it less than or equal to it it's to the left of it and everything that's greater than it is to the right of it which must mean that it's in its final assorted location and now this uh split at mute that that uh that gives us the left and the right we know that the pivot the left now has the pivot at its end which is where it should be so we can exclude that from left uh so we can actually do this by in a couple of different ways the ease the nicest one is probably just mute left actually we can also swap it to [Music] let's just split this at left and then have this be everything this might seem a little weird but uh remember that right is where the right hand side starts so if we split at left after swapping the pivot what we're really splitting is we're splitting at the pivot left split that mute oh wait no this should still be left minus one let me think here oh right uh left is already okay let me first do left is left plus one uh and let right is right plus one and right to point into um to account for the pivot at zero in theory we could have the math down here just sort of work out but this just makes it nicer to think about so now we swap the pivot into the end of left which is going to be left minus 1 because everything to the left is in left and everything to the left of left is in left so if we want to swap the last element to left it has to be left -1 and when we split we want to split we want to split where right starts if we split where right starts then everything to the left of that actually no this has to be minus one because we don't want it to include the pivot which is at the end of left um and now rather than having to slice this to not include the last element we slice this to not include the first element uh to avoid this you can choose the pivot at the middle of the slice then then you abouts you avoid some moves i don't think that's true if you chose the pivot in the middle you might run into a position where you have to shift the pivot around which sounds even more annoying partition at indexed use instead of split at mute will nicely exclude the pivot oh is that what partitioned index does really i feel like partition at partition at index yeah but that's cheating also it's nightly i mean partition at index just does quicksort for you which is not what we want uh and then here what we could do is like have a an assert for our own sake that um left dot last is less than right dot first or i guess less than or equal great uh why is this oh i guess we don't actually use right below here okay so now we have a working quick sort great so you see what i mean by this is a more complicated algorithm than the bubble sort or insertion sort of selection sort um but it is also a lot more efficient um and in fact let's try to evaluate a little bit how different these are right now so let's go ahead and add a benchmark so we're going to do is we're going to edit benches let's do main.rs now there are many ways to actually do this evaluation and i'm not gonna i don't think i'm going to uh pull in anything like criterion here instead what i'm what i'm interested in is comparing how many comparisons these different algorithms do which is a good proxy for for their complexity it's not quite equal to their complexity but it gets there um the other thing i realized is that for insertion sort this needs to be a public field if we want to be able to actually access it these should be pub use so now if we look at the oh man bench is made so we want to use uh horst star um and the way we're gonna go about evaluating this is we're gonna have our own little sorting type um so like sort of or i guess yeah sort evaluator it's going to be generic over t and we're going to derive actually we're not i'm going to show that in a second it's going to hold a t but it's also going to have hold a um [Music] which is going to be a sync atomic atomic u size um and actually we're going to want arc here too and i think you probably see where this is going i'm going to implement i have to implement all these traits manually that's pretty annoying so we have to import partial eek for sort evaluator the reason we have to implement all these manually is because i want all of them to compare only the t and just ignore comps but what comps is going to do is every time we compare an element we're going to increment the counter and this gives us a nice way to like run a sort and then at the end see how many comparisons did it do uh okay so eek i think is an empty trait partial leak is not let's pull that up here so we have to implement this thing which is easy enough this is just going to be self.t equals other dot t but we are going to do self comps fetch add one uh all right i also need ordering uh we i'm not gonna actually talk about how ordering works here uh and right hand side is just gonna do self can i avoid that yeah i can great and then we have to do the same thing for ord this is like a little bit annoying boilerplate um and for partial ord uh will we also count swaps no so there isn't really a good way to count swaps um because no method is called when two values are swapped so we don't really have a way to count that we would need the like implementation to cooperate with us like we could have like a trigger that it's supposed to call but that seems somewhat annoying oh no we're also going to end up with two types called ordering because there's atomic ordering and then there's standard compare ordering and these are of course different types uh so i'm just gonna do this instead and this again is going to be basically the same thing as here but it's going to do self dot t partial computer uh and for ord uh for org uh this is just gonna forward to self.t dot computer now you might wonder well why don't we add in this case oh ah other dot t other dot t uh the reason we don't do that is because usually compare forwards to partial compare i guess in this case actually we know that we're really testing ord so ord is the right thing to deal with here even eek we don't actually need to count uh was this faster than just using criterion so um the reason i don't want to use criterion here is both because it pulls in a bunch more complexity that i don't think is that interesting in this case and because criterion wouldn't measure this so with criterion what you get is an estimate of runtime and it's not we could measure the runtime here but i specifically want to look at the complexity which is related to runtime but not quite the same and this gives us an estimate of um of the runtime uh it's true we could use relaxed actually because this is all single threaded in fact we could use rc too but it doesn't matter because we're not measuring the runtime performance um so what i'm imagining here is we're going to do like for n in let's say so what sizes do we want to evaluate like arrays of size 0 1 10 100 1000 10 000. and then we're going to do is we're going to have like multiple iterations let's say 10 iterations of each one for each one we're going to construct a a list of values and of course this is not actually going to be a vector where all the values are the same i'm just this is just a placeholder for now um and then what we're going to do is um sort of uh i guess let up here counter is going to be arc new atomic u size new zero and each of the values in this array is going to wrap some value but all of them are going to point to the same single atomic use size so we get a full number of comparisons and then we're going to do is we're going to reset that counter store zero uh fine this i guess this will have to be relaxed uh relaxed uh we're gonna store zero in that counter before we start each iterate each um uh each actual um sort so let's start with something like bubble sort uh we're gonna do bubble sort dot sort and we're gonna give it a mute to values now because the the reason why i construct values at the top here is we actually want to run the different algorithms on the same array of values in the same order because otherwise we can't really compare how many comparisons they do so we're going to do sort of a for each one we're going to do a let values equals values.clone reset the counter and sort values then we're going to drop that clone of values i guess left hook equals this uh and in fact this could be a much nicer like we could have this be a little closure that takes takes a sorter and does this for us and then took is going to be bench of bubble sort and then we can also do insertion sort smart true we can do insertion sort smart false we can do selection sort and we can do quick sort and this is going to be a slice uh is there performance difference between using atomic size and sell u size if you only use one thread there is a little bit um like we we totally could use uh something like cell here in fact sure why not so we'll use cell and rc uh instead of these and the reason we can do this is because we don't actually need this to be thread safe and then this is just going to be self dot comps dot store self comps load plus one now it's get and set i think great and this is gonna be rc new cell new zero and this is going to be get actually this is going to be set nice this complains because right this uh this is actually going to be a oh right no this is going to be sorter here and this is gonna be a uh ref uh let's have this be a gin sorter that seems nice sorter cannot be made into an object ah it's not object safe annoying all right fine we can write this as a separate function too it's just it makes me sad um so that means it's going to take a t that implements ord it's going to take an s that implements sorter and it's going to take it's going to take the s it's going to take a slice of tea and it's going to take a reference to a cell of you size and it's going to return a u-size and then inside it's going to do this thing oh i thought that was a from slice but maybe i'm wrong i guess we can just do values dot error dot cloned dot collects right so this also needs time for my clone that's what i wanted to avoid uh but at least now we can do this it takes three arguments so now for each one we're gonna have to give it uh values oops values and counter counter i'll use counter i'll use counter great uh it the reason it's not the reason the trait is not object safe is because we have a method that's generic in it we can't box the sorter because the trait is not object safe because it has a generic method on it i'm probably not going to go through what object safe means because it's somewhat complicated and it the stream is already going a little long can't you simply sort sort evaluator instead of t uh that is what we're going to do actually this is going to be a sort evaluator of t uh which also means that we need to derive clone for this which is fine uh and i guess yep um oh right you're right we can just use tuvak i'll use dot 2 great um all right so uh now the question becomes how do we construct the thing that we're actually gonna test um and here the easiest thing is probably to pull in the rand crate is rand even a 1.0 yet it might not be zero seven all right so we're gonna do this i think there's like a rant to just generate a whole threadrng it implements rng core which gives us where's the rng trade there's been so much modifications of this great there we go rng i want to gen i think it can just generate a vector but even if it can't um back with capacity n and then we're going to do 4 and 0 to n [Music] values.push sort evaluator and the t is going to be i guess we need a we need an rng which means we need to use rand prelude star so we're just going to generate a bunch of random values i guess we can rant dot gen uh and the comparisons is just going to be a clone of counter which i guess technically they want us to write clone this uh and here we want it to generate a you size just say we're gonna sort numbers for now all right and now we can actually have this print out uh a bunch of values specifically it should print out um bubble then it's going to print out the n and then it's going to print out how long how many comparisons that took similarly here this is going to be insertion smart this is going to be insertion dumb this is going to be selection and this is going to be quick all right cargo bench see we get yeah prop test would let us generate these two um why did it is it just bench oh i need to declare it don't i path equals no i don't think i should have to uh i thought bench would just do this i mean that's fine we can just move benches to be source bin uh and then move source bin main to be sore spin bench ooh quicksort panicked that's good uh the length is 2 but the index is a very large number and quick sort at 24. so it seems like quicksort is not quite done line 24. um [Music] interesting uh a right can underflow can left ever overflow yeah that's not ideal how do we want to deal with this though i guess left won't really overflow that seems unlikely but right can underflow i think the way i want to deal with this is to have them be um i kind of want to have them be eye sizes rather than trying to deal with the rather than deal with the underflow um write can definitely underflow here imagine that all the elements get added to right right will end up moving one past zero and then we do one more execution um although i guess this is so the wild conditions should check that if right ever becomes no right becomes equal to left and right becomes zero so we continue executing we decrement right right underflows yeah right underflows left is still less than less than right we execute this line and right is now a big number so um i i mean there are a couple of ways to deal with this the easiest one is to just have these be eye sizes uh but that's also not great [Music] um uh it can't be a saturating sub either because we need to detect the case when left and right cross that's when we're done uh so i think the yeah i guess that's true i guess one easy way to do this is while right is greater than equal to zero and this but that i get okay this is this is awful but that would be the way to do it because underflow um which also in debug mode would not work because in debug mode uh this panics no we we do have to decrement right because otherwise we don't detect detect the way exit um so it it it's not like the the decrement is not wrong the decrement does need to be there it's just the decrement causes it to not realize that we have to exit um so like right rapping sub one like it's awful but um i also realized one one other thing we can do over in the benchmark oops uh bench is that um we only need to generate this once for every n and then each of the iterations we can just do values dot shuffle and that will work just as fine uh it won't work in debug mode because um in debug mode rust panics on overflow and underflow yeah so so the other alternative is some people are wrong file uh the other people the thing that some people are pointing out is can't you just check here like if right is zero then break so that that is another way to do it i don't know if it's nicer i mean okay so it would be right uh my minus equals one this would stay right equal minus equals one it would be uh if right is zero then break and it'll be the same here it's more verbose but you know uh we could also use check sub uh it still ends up being pretty verbose okay so this now runs although quick check apparently is doing no comparisons which seems not quite right in fact it's reporting no comparisons for insertion dumb or quick or bubble that's because they all use partial compare so the the less than operator and the greater than operator in rust both call partial compare not compare so there are two ways to solve this one is to not use those operators and use call compare directly um and the other is to move this into partial compare um oh my why is this being annoying this is the file i want so we can move this into partial ord um actually yeah that's the way to go about it do this and then have this do self dot partial compare other dot uh unwrap uh [Music] uh is there a reason the loop body needs to run if left equals right yes yeah we're not done if left equals right that means there's one element we haven't looked at yet uh is incrementing left correct yeah incrementing left is fine because it's not going to overflow in theory left good overflow um but it's but like overflow is a very large number underflow is not a very large number because any any small array is gonna trigger it um can you check the list is sorted after bench just to be sure sure uh values i think there's an is sorted yeah um oh it's not fine um oh that's four i and one two values.len technically it's this but that's a nightly thing so instead we have to do it ourselves uh and we want to assert that values i is greater than or equal to values i minus 1. [Music] yep that seems to be the case i think we should have right equal length instead of length minus one no can't you increment on both or since the ord implementation will never call ord on the wrapper but only on t um oh we could do that too you're right um because this ends up redirecting or ends up calling directly to the t uh we can do this you're right and in fact we can do the same thing for uh equality won't checking if the array is sorted also income of the counter yeah you're right you're completely right uh let uh count is this and then we check and then we count oops all right so this is now at least giving numbers currently those are a lot of numbers and they're not very easy to to get at so let's stick them in like values dot dat how bad is it using nightly for binary i just prefer to not use nightly if i don't need to um but it's not bad to use nightly it's just like inconvenient usually now i guess to to end this let's i was sort of hoping we would get to merge sort and heapsort because they're kind of interesting at the same time i think we've covered a bunch of potentially interesting like rust topics so i don't think we need to like the goal of this again is not really sorting algorithms it's more about how we implement them but i do want to plot these just to give you a sense of what this looks like so let's see if what's the easiest way for me to do this um so we could cut that into gnu plot dash p dash e plot using uh one i'm using two colon three title one let's see if that does what i wanted to do no that did not really help ah i thought there was a way for you to tell new plot to use a given field as the title no yes see i want to avoid having to write a complicated script but maybe i can't really get away from it uh all right fine we'll do it in another way uh let's just write a simple r script because our scripts are nice so we're going to do t is read.table values and in fact let's stick some headers on here and say this is um this is algorithm n and comparisons um we want to include uh ggplot2 and then we want ggplot2 let me have the pull up the quick start here somewhere that's not oh quick guide great that's not a quick guide you're lying to me that's terrible all right so this library i very rarely write our code i just have this like same plotting script that i keep just um copying over and over again but it does produce really nice visualizations this is not an official guide this is a bad guide give me the real guide here we go uh that's what i want so i want uh t and i want the x to be n i want the y to be comparisons and i want the color to be the algorithm and i want it with points uh no hmm oh fine uh library ggplot2 this uh was not intended to become a uh r tutorial all right it shows what great so it pulled in t correctly and now i want this line up here object n not found is that not what i called that column oh that's because i'm stupid uh headers equals true huh our re table uh we know pivoted to the crust of r yeah i know right you missed tight algorithm i probably did that too um is it titles there's definitely a a header i'll go right i've written right so many times that uh beautiful all right uh and let's have this also with uh gm point plus gm smooth right this might not be very easy to see because the font size is kind of bad but here what we have is along the x-axis is the length of the array the y-axis is how many comparisons did you do uh and then this shows the the sort of the relationship between the two right um and you can see that this is not this is not good for bubble sort right you can see how bad bubble sort is right uh you can also see that the uh let's see so insertion dominant insertion smart are almost the same and this should not be surprising right oh my head is in the way sorry let me go ahead and do me i'm still uh where is the well that's fine i can just do this instead um that should be easier to look at so you see that the difference between insertion sort smart and dumb is basically zero this shouldn't be terribly surprising so if you remember back to what the algorithm actually does the algorithm was just we do a binary search for finding the insertion point but we still need to uh we still need to do all the swaps actually maybe that's weird yeah the the the number of um the number of comparisons you do is still just very very large the fact that you do less for each insert doesn't end up mattering as much as the overall algorithms just have to do a lot of comparisons bubble sort of course terrible selection sort is worse than insertion sort which is also what wikipedia told us it would be but the implementation was simpler it uses less memory right so that's nice uh and quicksort you see is just way way smaller right we can we can totally compare this with uh the standard library sort too if we want here so let's add a benchmark of the standard library sort so standard sorter uh so i'm gonna go ahead here and do this uh all right so let me read that in again and then plot it uh you wanted log y so let's go ahead and look at what that is i forget i think it's just gg log y uh scale y log 10 scale y log 10. oh did i do something silly again i must have but i don't quite know what oh right last time i modified values to have a header so that's algorithm n and uh comparisons all right so this is log scale so that makes it a little hard to read um quick sort is now duplicated uh header is gone yeah headers is missing oh yeah we can make the x-axis logarithmic instead uh actually let's do let's maybe do both so we're going to do um scale x log 10 as well okay so this is at this point a very weird plot uh but keep in mind here that a straight line here i guess the smoothing is at this point fairly unhelpful where do we have right so the colors have changed so we have quick sort down here the standard library sort is down here selection sort bubble sort insertion dumb insertion smart is down here why that seems weird oh it's yeah it's because um okay so yeah let me turn off the smoothing i'll leave it um okay so insertion sort smart the reason it looks like insertion search smart is so good here is because this is remember only measuring the number of comparisons it is not measuring the number of swaps right so it's not really the complexity of the algorithm it's just the complexity in terms of number of comparisons and if you remember for insertion sort the insertion sort dumb right does a comparison for every swap insertion sort smart does very few comparisons but it does the same number of swaps so really the figure here is giving us a skewed image of what's going on because we can't also measure the the swaps themselves now of course uh if we did this with runtime we'd get a picture that was much noisier but it would include the cost of things like swaps um uh there are algorithms that do zero compare so they uh well sort of uh those are counting algorithms that generally only works for things like numbers um and they can get complexities below and log in yeah the smoothing function is not great for this particular use case nice um we could we can totally compare the actual runtime too um here let me type that up real quick um so we're gonna have this in outside a u size and an f64 uh let time is time instant now it took is time elapsed uh and then we want count and took the assets of 64. and now we can do this this this [Music] i should really have written just like a quick macro for this but i did not i was a fool took.0 took dot one zero one zero one zero one zero one run this again uh i think my computer has enough course that this shouldn't really matter because it's a single chord experiment anyway algorithm uh n comparisons and uh time so now let's first let's stop this insane scaling and keep gm smooth probably we want the y-axis now to be time whoa this this smoothing is just like not helping let's let's get rid of that smooth uh i guess technically this is a scatter i forget maybe they don't have scatter so this is going to be much harder to read so this is now log y scale still so all the lines would have gone like this if they were smoothed yeah so the runtime is very very hard to read but here you'll see that both quick sort and the standard library sort are generally much faster insertion smart is faster than the dumb insertion sort because it has to do fewer comparisons but it's nowhere near what the standard library in quick sort managed to do so here we see that the the delta here right is that we're also counting the swaps but we do get a much noisier signal you see how easy that was to switch up though which is nice all right let's do a log x as well and see scale x log 10. nice so gm line will not do what you want here because there are multiple points for every x point um so gm line will do something weird although it'll actually it might not look too bad but it's not really what you want yeah it ends up drawing a line um it ends up drawing a line between the data points for the same x coordinate too but regardless yeah so here you see just how much of a difference is right remember that this is log y scale so the difference here is is quite large uh be right like insertion the the smart insertion sort is a much better than the dumb insertion sort nice um okay i think that's all i wanted to go through today i think like it could be interesting to implement more sorting algorithms but i suggest that something you just sort of take on yourself like it's just fun to implement these algorithms anyway and it teaches you a bunch of just nice things about um how to write rust code um what i'll do is i'll post this as a git repository like i'll publish it on github and feel free to like if you have additional implementations of algorithms just like post them and and we'll keep a little repository there for people to look at um are there any questions before we sort of end for the day this ended up longer than i had planned but you know it's because it's fun um can we try an all decreasing slice i think quick gets pretty bad with that so uh currently we're sort of randomizing them which means that the the range you see right you could think of the bottom is more like best and the top is more like worse in the middle as sort of the average but we need way more data points to actually sample the whole thing we could generate sort of known worst and best-case scenarios but i don't think it adds too much value to this particular stream right remember this is not really a stream on comparing sorting algorithms because like you would probably use something like tim sort instead you wouldn't actually use any of these um and you would use like i think um tim sword is really like a merge sword combined with quick sort or merge plus selection sort i forget um so i don't think it's worth digging too much into these uh it's more about the rust code we ended up writing sweet all right thanks everyone thanks for watching i hope that was interesting uh in a week or two i will do a stream on um this this modification i want to make it to evmap that will be a much more complicated stream in some sense like this is sort of a more of an introduction sort of introductory stream to rust or or for those who are not that familiar with rust in and of itself whereas the evmap stream will be more like the older streams i did with our like pure implementation streams um it will probably be longer uh and it will deal specifically with like concurrent data structures and and abstraction around them i think it will be really interesting uh but it will be a different flavor to this one so um keep an eye out i'll i'll post on twitter whenever i know when i end up doing it and of course as usual i'll post the recording on youtube afterwards alright until next time see you all bye

Channel: Jon Gjengset

Views: 26,184

Rating: 4.9374113 out of 5

Keywords: rust, live-coding, sorting, algorithms

Id: h4RkCyJyXmM

Length: 157min 52sec (9472 seconds)

Published: Sat Nov 14 2020

Reddit Comments

[u/leviathon01]

I love this series.

[u/OS6aDohpegavod4]

orst is genius

[u/allsey87]

u/Jonhoo would you consider doing a Crust of Rust on the more advanced aspects of traits in modern Rust? I am thinking about how and when to use impl, dyn, supertraits, and the Sized trait, what problems they solve, and implications on your code (e.g., monomorphism vs. polymorphism)

[u/Elendol]

very interesting video and series (tbh from the thumbnail I thought you found a way to make ggplots from Rust and/or easily call Rust from R, and I would love that, my two favourite things right now combined)