25:50 "1..slice.len()" is actually much better than "0..(slice.len() - 1)" because the latter will panic on an empty slice. You always have to be careful with subtracting from unsigned numbers like usize.
@@meteora4478 They are really annoying. I think that's at least the third time I've gotten comment responses from them and reporting them to YT doesn't seem to help. I really don't get what they are trying to achieve since I can't imagine anybody will fall for such an obvious completely random message but I guess I'm probably wrong.
Terrific content. Very useful. As an nvim user I'd also be interested in the video showing the keys being types at the bottom right. You do movements that are clearly better than mine and that would be a straightforward way to add value to the content for nvim users. Many times I wanted to go back and see how you performed certain operations. Cheers,
The Quicksort algorithm I read in a book (Introduction to Algorithms 3rd Ed.) uses pointers both starting from the left, instead of one on the left and right each. That approach avoids the entire underflow-conundrum you had with the right pointer, avoids the off-by-one shenanigans by moving the pivot to the end of the array instead of at index 0, and is also simple to do in a basic for loop without needing to compare the left and right pointers
I always found playing cards to be a great example for sorting stability. A stable sort ordering them by the number will for example leave the black 8 before the red 8 if it was there before.
Insertion sort has a special property of having a nearly linear time for almost sorted sequences. This makes it perfect as a last step in combination with other sorting methods. Quicksort is actually implemented as a regular quick sort steps until a certain threshold(10~15 elements) + insort. That last mile of recursion descend is very expensive. Also, binary search optimization doesn't make much sense. It is a valid optimization for the insertion sort, but in practice it doesn't make sense. It's a quadratic sort, so at the time the log N will start making a difference, the overall cost is already too high. Just use different method. And for almost sorted sequences, when this sort really makes sense, binary search is less cache friendly.
Binary search optimisation might make sense if you order not the actual slice which you already have whole, but when you have a “stream” of data which arrives asynchronously one element at a time, with delay between elements. You can then always keep what you already have sorted easily with insertion sort, while other methods might not be applicable. Then binary search might save you some cpu time.
If you plan on making more videos in the future, one thing I think would be cool would be to crack open some large open source rust projects like Redox (OS), and just find interesting things to comment on. Probably tons and tons of interesting techniques / rustisms in a project like that.
26:37 You can require only one type parameter(S) by using 'impl Ord'. If you make the function signature 'fn sort(slice: &mut [impl Ord])', the callers can't provide the type for T.
I had a lot of fun trying a quicksort implementation just from the Wikipedia definition before watching the rest of your explanation.. ran into similar issues as you did 😂
For the quicksort underflow of right, I would instead special case left == right. In the body, three things can happen: left is incremented, right is decremented, and left and right can swap. Clearly the swap doesn't matter, though it turns out the right swap optimization will always be true anyway, so the only thing that matters is if left is incremented or right is decremented. Right doesn't get used after, which is unsurprising as it must be left - 1. So all we care about if we should increment left, a simple if pivot > rest[left] { left +=1; }, and make the loop test left < right
Things to read on sorting and search: 1. Donald Knuth, Volume 3. (Obviously) 2. Niklaus Wirth, Algorithms + Data Structures = Programs. (Optional) 3. Jon Bentley, Programming Pearls.
I was thinking `right = theSplitSlice.len()` and then change what `right` means to be one more than the previous meaning of `right`. Some of the math changes a bit, but if you in general do everything by left-closed intervals, you tend to not screw it up. (At least I'm like that.)
2:24:25 "insertion-smart is almost the same as insertion-dumb" No, it's in fact better than quick. Look at the raw numbers on the left. You don't see it on the plot because it's below quick. EDIT: Realizes it at 2:29:33
2:08:00 Just break early ``` } else if &rest[right] > pivot { if right == 0 { break; } right -= 1; } ``` and similar in the `else`. EDIT: Does it later in 2:13:00
In the bubble sort implementation, I think it would have been more idiomatic with .windows_mut(2) and std::mem::replace. It would avoid the error prone slice indexing
It appears that the insertion sort implementation matches the "Optimization" section of Gnome sort on Wikipedia (en.wikipedia.org/wiki/Gnome_sort) which apparently is dubbed "stupid sort" which is hilarious considering the "if !self.smart"
Hi Jon :) Great work, thank you and keep up :) I am just learning rust, coming from python, so might be stupid question. Why go with creating a trait for this library and not just go for functions with generic types for every sort algorithm and keeping the same API. The question is, how you decide on then to choose what? Thanks a lot, once again!
In insertion sort - wouldn't it be more efficient to binary search the insertion point in the sorted part, instead of walking right to left or left to right? You'd still end up swaping the same amount of memory, but at least you'd do O( log n) comparisons instead of O(n) . Edit: lol, just a second after resuming, they talked about binary search. Great minds....
Correct me if I am wrong, isn't bubble sort's last end sorted after every iteration, cause after every iteration, in bubble sort, the biggest element is pushed backwards. Bubble sort is [unsorted | sorted] and insertion sort is [sorted | unsorted].
Bubble sort is [anything | correct] and insertion sort is [unsorted | sorted]. The leftover parts of bubble sort are in their final correct position, the leftover parts of insertion sort are only correct relative to each other. And the leftover parts could be at the start or end, doesn't matter. Bubble sort and insertion sort have the same sorting network though, so in that way they are equivalent.
I really want to try to implement a radix sort here. Not everything can be radix-sorted. But usize can be radix-sorted, and your benches use usize. So that's nice. However, I have tried to dance around the generics and the trait bounds for quite a while now and not figured out how to correctly tell the compiler that I want to implement Sorter for my RadixSort, but only for when T is usize. Can it be done without having to change the Sorter trait itself?
Ah, no, unfortunately I think you'll have to move the generic T to the Sorter trait. That said, that might be a good idea anyway! Especially because it would also make the trait object safe again, which would be a major win.
The binary search strategy in insertion sort won't work, cause it will give err always as the element we want to insert will not be present in sorted section. Edit: Never mind, I saw that rust binary search implementation gives expected index in error case. That's clever.😁
Could you write `trait Sorter: Fn` which default-implements `sort` via `call`? Then just `impl Sorter for bubblesort;` rather than making these OOP actor structs
I noticed I always wanted to use for loops instead of while. Since I use rust I see people using loop/while alot more.. is this a rust thing or really just preference ?
Maybe in looking at rust code you're seeing more technical code is all? For loops are definitely more common even in rust. Conceptually they're very different loops in my opinion. "For" is really about applying the same operation on all members. "While" is about achieving a result that doesn't have a clear mapping to what's being iterated on, you just apply an operation as many times as you need to get there (hopefully you've proven to yourself you will always get there) Most code out there is about processing data linearly, or aggregating it in some manner. If that's the case it's nice to have a concise way of showing it's not a logical loop and there's no risk of it looping forever. It's a "safe" version of looping. Most algorithms that would require you to use more complicated logic are conveniently packaged in built-in functions or libraries. It just so happens people who write rust tend to write libraries or otherwise more math-oriented algorithms. I find loop to have a similar use. The main difference being there's multiple ways you can exit the loop and none is clearly more common, and writing a single condition would be painful. Then you can just break out where relevant, and it's probably more readable that way.
You can't sort a stream without collecting it into a vector, because the last element of the stream might be the first thing you have to output. Sort is a classic batch problem that can't be solved in an online way.
@@lizzienovigot The entire stream isn't sorted until you get to the end of the stream. For sure you can sort the *start* of a stream with insertion sort. Insertion sort is actually even pretty efficient for keeping a stream sorted, and it's one of the few places where a linked list can work better than a vector also.
@@darrennew8211 sure, but thats not my point. My point is that you can have sorting algorithms for online data which are implemented without waiting for the whole data first, so saying " Sort is a classic batch problem that can't be solved in an online way." is just plain wrong. In theory stream can even be "endless" and you can still have an algorithm that keeps the data already arrived always sorted.
@@lizzienovigot Yes, that's fair. You can sort the data as it comes in. But if you want to sort *all* of the data, you have to have it all inputted before you can output anything. That's what a "batch" algorithm vs an "online" algorithm means. Contrast with something like laying out text, where you can output the line breaks and page breaks for the first page of text before you've seen the tenth page of text. When you talk about the properties of *problems* instead of *solutions*, you talk about their inputs and outputs, not how they process things internally. Like when you talk about algorithms, you measure efficiency as O(N) but when you talk about problems you talk about Θ(N). No cleverness of programming will let you print out the smallest number from an unordered list of numbers before you have seen all the numbers.
Depends on whether the function needs ownership or not. If it does, it is typically best to leave it up to the caller how to get an owned value. Into can also be helpful
impl AsRef will let you pass &str, but also String, Cow and any other string like things by value. At the low, low cost of you needing to do the as_ref() call inside yourself, and making every call with a different type generate separate machine code. (Check out the std::fs methods for a trick here)
In general you get these through "Code Actions", which are a feature of rust-analyzer, the language server for Rust. It's probably pretty easy to set up with VSCode, but I haven't tried to do so myself :)
@@jonhoo Hold up, this video wasn't a fundraiser? I see fundraiser right below the title of the video. There is a donate button for GiveDirectly saying "Give Money to Poor People." What's going on here?
@@lonnybulldozer8426 Ahh, no, that's a new TH-cam thing. They've started showing ads on all videos even if the creator has monetization turned off (which I always have), and creators who do not actually monetize can set a charity for that ad income to go to instead. In my case that's the "Give Money to Poor People" project. But TH-cam is clearly very bad at labeling it 😅
@@jonhoo merge sort keeps a work array, so there needs to be more than 1 of the value at a time hence the Clone. see www.reddit.com/r/learnrust/comments/jfvd4o/out_of_place_sorting_merge_sort_with_noncopy_types/ for a discussion about implementing merge sort without Clone.
Yeah, I was about to suggest you'd do it with an unsafe alias of the type. Making sure you never double-free even in the case of panics will probably be tricky though.
Do you know Martin Gjenset Herstad, he is my friend from Norway. He has a girlfriend named Diana and they are Together 24/7. I will say hello from you to Camilla and Øyvind:-)!
25:50 "1..slice.len()" is actually much better than "0..(slice.len() - 1)" because the latter will panic on an empty slice. You always have to be careful with subtracting from unsigned numbers like usize.
Good point
What are these bots lmao
@@meteora4478 They are really annoying. I think that's at least the third time I've gotten comment responses from them and reporting them to YT doesn't seem to help. I really don't get what they are trying to achieve since I can't imagine anybody will fall for such an obvious completely random message but I guess I'm probably wrong.
@@1vader a few people might fall for this, it’s a numbers game I guess. Though I don’t think I’ve seen one of these before.
@@meteora4478
They are gone now. You did it.
Terrific content. Very useful. As an nvim user I'd also be interested in the video showing the keys being types at the bottom right. You do movements that are clearly better than mine and that would be a straightforward way to add value to the content for nvim users. Many times I wanted to go back and see how you performed certain operations.
Cheers,
The Quicksort algorithm I read in a book (Introduction to Algorithms 3rd Ed.) uses pointers both starting from the left, instead of one on the left and right each. That approach avoids the entire underflow-conundrum you had with the right pointer, avoids the off-by-one shenanigans by moving the pivot to the end of the array instead of at index 0, and is also simple to do in a basic for loop without needing to compare the left and right pointers
I always found playing cards to be a great example for sorting stability. A stable sort ordering them by the number will for example leave the black 8 before the red 8 if it was there before.
Insertion sort has a special property of having a nearly linear time for almost sorted sequences. This makes it perfect as a last step in combination with other sorting methods. Quicksort is actually implemented as a regular quick sort steps until a certain threshold(10~15 elements) + insort. That last mile of recursion descend is very expensive.
Also, binary search optimization doesn't make much sense. It is a valid optimization for the insertion sort, but in practice it doesn't make sense. It's a quadratic sort, so at the time the log N will start making a difference, the overall cost is already too high. Just use different method. And for almost sorted sequences, when this sort really makes sense, binary search is less cache friendly.
Was going to say just this. Insertion sort has 2 advantages, speed on short lists and speed on sorted lists. Binary search ruins both of those.
@@CarrotCakeMake Insertion sort on its own is also stable. Using binary search precludes stability unless you exert extra effort to maintain it.
Binary search optimisation might make sense if you order not the actual slice which you already have whole, but when you have a “stream” of data which arrives asynchronously one element at a time, with delay between elements. You can then always keep what you already have sorted easily with insertion sort, while other methods might not be applicable. Then binary search might save you some cpu time.
*Casually drinks from his Ph.D mug*. Congrats, Jon!
(This was posted before he explained the mug)
Really enjoyed this stream! A lot of fun and interesting stuff, especially the or pattern in the let statement which was totally new to me :)
If you plan on making more videos in the future, one thing I think would be cool would be to crack open some large open source rust projects like Redox (OS), and just find interesting things to comment on. Probably tons and tons of interesting techniques / rustisms in a project like that.
This is really informative, I can't even begin to list the things I've learned. Thank you!
26:37 You can require only one type parameter(S) by using 'impl Ord'. If you make the function signature 'fn sort(slice: &mut [impl Ord])', the callers can't provide the type for T.
I had a lot of fun trying a quicksort implementation just from the Wikipedia definition before watching the rest of your explanation.. ran into similar issues as you did 😂
For the quicksort underflow of right, I would instead special case left == right. In the body, three things can happen: left is incremented, right is decremented, and left and right can swap. Clearly the swap doesn't matter, though it turns out the right swap optimization will always be true anyway, so the only thing that matters is if left is incremented or right is decremented. Right doesn't get used after, which is unsurprising as it must be left - 1.
So all we care about if we should increment left, a simple if pivot > rest[left] { left +=1; }, and make the loop test left < right
43:47 "that's a rotate!" :)
Things to read on sorting and search:
1. Donald Knuth, Volume 3. (Obviously)
2. Niklaus Wirth, Algorithms + Data Structures = Programs. (Optional)
3. Jon Bentley, Programming Pearls.
HEY!! I JUST DID MY THESIS DEFENSE TOO. It was Rust related too :D
Link?
Cool! What was it on?
Better solution for right underflow with QuickSort (in my opinion): just start with left = 1, right = slice.len() - 1 and index into the slice :D
I was thinking `right = theSplitSlice.len()` and then change what `right` means to be one more than the previous meaning of `right`. Some of the math changes a bit, but if you in general do everything by left-closed intervals, you tend to not screw it up. (At least I'm like that.)
2:24:25 "insertion-smart is almost the same as insertion-dumb"
No, it's in fact better than quick. Look at the raw numbers on the left. You don't see it on the plot because it's below quick.
EDIT: Realizes it at 2:29:33
50:29 nice mug!
2:08:00 Just break early
```
} else if &rest[right] > pivot {
if right == 0 {
break;
}
right -= 1;
}
```
and similar in the `else`.
EDIT: Does it later in 2:13:00
the final else branch in the quicksort while loop , is the right underflow necessary?
In the bubble sort implementation, I think it would have been more idiomatic with .windows_mut(2) and std::mem::replace. It would avoid the error prone slice indexing
1:52:30 why dont you count PartialOrd and PartialEq?
NGL I copied your init.vim for rust and you have the CocAction command at .
It appears that the insertion sort implementation matches the "Optimization" section of Gnome sort on Wikipedia (en.wikipedia.org/wiki/Gnome_sort) which apparently is dubbed "stupid sort" which is hilarious considering the "if !self.smart"
at 50:00 you can do
let Ok(i) | Err(i) = slice[..unsorted].binary_search(&slice[unsorted]);
oh he mentions that like 1 minute later :)
Hi Jon :) Great work, thank you and keep up :) I am just learning rust, coming from python, so might be stupid question. Why go with creating a trait for this library and not just go for functions with generic types for every sort algorithm and keeping the same API. The question is, how you decide on then to choose what? Thanks a lot, once again!
In insertion sort - wouldn't it be more efficient to binary search the insertion point in the sorted part, instead of walking right to left or left to right? You'd still end up swaping the same amount of memory, but at least you'd do O( log n) comparisons instead of O(n) .
Edit: lol, just a second after resuming, they talked about binary search. Great minds....
Correct me if I am wrong, isn't bubble sort's last end sorted after every iteration, cause after every iteration, in bubble sort, the biggest element is pushed backwards.
Bubble sort is [unsorted | sorted] and insertion sort is [sorted | unsorted].
Bubble sort is [anything | correct] and insertion sort is [unsorted | sorted]. The leftover parts of bubble sort are in their final correct position, the leftover parts of insertion sort are only correct relative to each other. And the leftover parts could be at the start or end, doesn't matter.
Bubble sort and insertion sort have the same sorting network though, so in that way they are equivalent.
I really want to try to implement a radix sort here. Not everything can be radix-sorted. But usize can be radix-sorted, and your benches use usize. So that's nice.
However, I have tried to dance around the generics and the trait bounds for quite a while now and not figured out how to correctly tell the compiler that I want to implement Sorter for my RadixSort, but only for when T is usize. Can it be done without having to change the Sorter trait itself?
Ah, no, unfortunately I think you'll have to move the generic T to the Sorter trait. That said, that might be a good idea anyway! Especially because it would also make the trait object safe again, which would be a major win.
@@jonhoo Seems easy enough, though. Just didn't want to change your files just to try to shoehorn in my own ideas, before making sure it is necessary.
why is the rust selection sort so slow? also the approach you used is 2x as slow as the for loop
The binary search strategy in insertion sort won't work, cause it will give err always as the element we want to insert will not be present in sorted section.
Edit: Never mind, I saw that rust binary search implementation gives expected index in error case. That's clever.😁
39:52 Should be `slice[..unsorted].binary_search` since only that part of the slice is guaranteed to be sorted.
EDIT: Fixed in 43:06.
Could you write `trait Sorter: Fn` which default-implements `sort` via `call`? Then just `impl Sorter for bubblesort;` rather than making these OOP actor structs
Thanks jon
I noticed I always wanted to use for loops instead of while. Since I use rust I see people using loop/while alot more.. is this a rust thing or really just preference ?
Maybe in looking at rust code you're seeing more technical code is all? For loops are definitely more common even in rust.
Conceptually they're very different loops in my opinion. "For" is really about applying the same operation on all members. "While" is about achieving a result that doesn't have a clear mapping to what's being iterated on, you just apply an operation as many times as you need to get there (hopefully you've proven to yourself you will always get there)
Most code out there is about processing data linearly, or aggregating it in some manner. If that's the case it's nice to have a concise way of showing it's not a logical loop and there's no risk of it looping forever. It's a "safe" version of looping.
Most algorithms that would require you to use more complicated logic are conveniently packaged in built-in functions or libraries. It just so happens people who write rust tend to write libraries or otherwise more math-oriented algorithms.
I find loop to have a similar use. The main difference being there's multiple ways you can exit the loop and none is clearly more common, and writing a single condition would be painful. Then you can just break out where relevant, and it's probably more readable that way.
Can you share your script that you mentioned that generates nice visualizations?
Ah, it's not a script, it's an R library called ggplot2 :)
@@jonhoo Ha! Nice.
You can't sort a stream without collecting it into a vector, because the last element of the stream might be the first thing you have to output. Sort is a classic batch problem that can't be solved in an online way.
Not true, Insertion sort is exactly suitable for keeping “stream” data sorted.
@@lizzienovigot The entire stream isn't sorted until you get to the end of the stream. For sure you can sort the *start* of a stream with insertion sort. Insertion sort is actually even pretty efficient for keeping a stream sorted, and it's one of the few places where a linked list can work better than a vector also.
@@darrennew8211 sure, but thats not my point. My point is that you can have sorting algorithms for online data which are implemented without waiting for the whole data first, so saying " Sort is a classic batch problem that can't be solved in an online way." is just plain wrong. In theory stream can even be "endless" and you can still have an algorithm that keeps the data already arrived always sorted.
@@lizzienovigot Yes, that's fair. You can sort the data as it comes in. But if you want to sort *all* of the data, you have to have it all inputted before you can output anything. That's what a "batch" algorithm vs an "online" algorithm means. Contrast with something like laying out text, where you can output the line breaks and page breaks for the first page of text before you've seen the tenth page of text. When you talk about the properties of *problems* instead of *solutions*, you talk about their inputs and outputs, not how they process things internally. Like when you talk about algorithms, you measure efficiency as O(N) but when you talk about problems you talk about Θ(N). No cleverness of programming will let you print out the smallest number from an unordered list of numbers before you have seen all the numbers.
Calling a sorting lib orst is just genius
Radix sort?
In your functions, do you prefer passing string slices as arguments or owned strings?
Depends on whether the function needs ownership or not. If it does, it is typically best to leave it up to the caller how to get an owned value. Into can also be helpful
impl AsRef will let you pass &str, but also String, Cow and any other string like things by value. At the low, low cost of you needing to do the as_ref() call inside yourself, and making every call with a different type generate separate machine code. (Check out the std::fs methods for a trick here)
Hey Jon, how would someone do the shortcut for impl all trait functions in lets say vscode?
In general you get these through "Code Actions", which are a feature of rust-analyzer, the language server for Rust. It's probably pretty easy to set up with VSCode, but I haven't tried to do so myself :)
What was the fundraiser for? To buy yourself more D&D miniatures? If so, I might support the cause.
Which fundraiser?
@@jonhoo I'll support the one for the D&D miniatures. Whichever one that was.
I'm not sure I follow? There isn't a fundraiser on my channel I don't think? I do have an Amazon Wishlist though!
@@jonhoo Hold up, this video wasn't a fundraiser? I see fundraiser right below the title of the video. There is a donate button for GiveDirectly saying "Give Money to Poor People." What's going on here?
@@lonnybulldozer8426 Ahh, no, that's a new TH-cam thing. They've started showing ads on all videos even if the creator has monetization turned off (which I always have), and creators who do not actually monetize can set a charity for that ad income to go to instead. In my case that's the "Give Money to Poor People" project. But TH-cam is clearly very bad at labeling it 😅
how would you do merge sort? would you require `T: Ord+Clone`?
Why would you need the Clone bound?
@@jonhoo merge sort keeps a work array, so there needs to be more than 1 of the value at a time hence the Clone. see www.reddit.com/r/learnrust/comments/jfvd4o/out_of_place_sorting_merge_sort_with_noncopy_types/ for a discussion about implementing merge sort without Clone.
Yeah, I was about to suggest you'd do it with an unsafe alias of the type. Making sure you never double-free even in the case of panics will probably be tricky though.
Do you know Martin Gjenset Herstad, he is my friend from Norway. He has a girlfriend named Diana and they are Together 24/7. I will say hello from you to Camilla and Øyvind:-)!
library name sort of bubble
ggplot is nice.
Crust of R$(ust)?
It’s a shame your keyboard is so loud, this is the second video I stopped watching due to it. :(
haha