5 ms·
You're misunderstanding. They don't explain how to do partitioning at all. Step 3 is just tagging the elements that are above the partition element, which there
by f33d5173 1y ago
You're misunderstanding. They don't explain how to do partitioning at all. Step 3 is just tagging the elements that are above the partition element, which there happen to be two of.
- tialaramex 1y agoWell, to the extent a picture can explain they say choose at random. That's what the dice shown is about. A random pivot is... fine. It can't solve the worst case perf problem, and it won't ensure high performance for other cases either, but hey you did pick a pivot and this algorithm is often fast enough.
- f33d5173 1y agoI'm talking about step 5. The elements just magically migrate to the correct position, whereas in the real algorithm they would be moved individually.
- tialaramex 1y agoIt would be clearer if they weren't magically sorted early. Maybe they can improve in a later edition of the instructions. I think maybe Lego would cut away to show one layer of repetition for example.
- 010101010101 1y agoThe curly braces with the arrow pointing down are the thing implying the recursive calls on that set of elements until you’re done.
- f33d5173 1y agoyou're describing step 6