Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It looks like Step 3 may be using Hoare's original partitioning method with two pointers, which is laudable.


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.


Well, 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.


I'm talking about step 5. The elements just magically migrate to the correct position, whereas in the real algorithm they would be moved individually.


The curly braces with the arrow pointing down are the thing implying the recursive calls on that set of elements until you’re done.


you're describing step 6


It 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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: