News for hackers. Stuff that matters.

A comment on Branchless Lomuto Partitioning. Parent comment

Re:Branchless Lomuto Partitioning by stavros on Wednesday December 06, 2023 @07:32AM (#38542998)
Ahh, thank you, this clarifies things! I was thinking of Quicksort, where j moves left until it meets i, and missed the fact that they both move in the same direction and i runs through the entire list. Thanks!

EDIT: I'm now on the desktop and see that your graphs clarify this much better, on mobile I had Dark Reader and they were invisible. You may want a white background.

[ Parent | on HN ]
Re:Branchless Lomuto Partitioning by orlp on Wednesday December 06, 2023 @07:38AM (#38543061)
> I was thinking of Quicksort, where j moves left until it meets i, and missed the fact that they both move in the same direction and i runs through the entire list.

You were thinking of Hoare partitioning. Quicksort can use either Hoare or Lomuto (or any other) partitioning algorithm.

[ Parent | on HN ]
Re:Branchless Lomuto Partitioning by stavros on Wednesday December 06, 2023 @07:40AM (#38543074)
Yes, now that you mention it, that does make sense, thank you.
[ Parent | on HN ]