Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort explained IKEA-style

idea-instructions.com

Post reply on HN
Print view View original

131–140 of 142 posts

Re: Quicksort explained IKEA-style

#131

Post by photon_lines »

ksenzee wrote: post #129
nucleardog wrote: post #126

Earlier quoted context omitted.

> As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. I have no formal CS background or education at all, but have been working in IT for... over 20 years now? So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort spec…

If you’re an outlier, I’m out there with you: I’ve also been writing software professionally for 20 years, I have no CS degree, and I’m not fool enough to reimplement algorithms like quicksort that are sitting right there in stdlib. I similarly found this explanation a lot more useful than anything else I have read about quicksort, and I’m confident I could implement it now, but couldn’t have before I read this.

If you guys like visual-explanations that are a bit more intuitive -- I put actually made guides on both data-structures and algorithms not too long ago which you can find here:

Visual-Focused Algorithms Cheat Sheet — https://photonlines.substack.com/p/visual-focused-algorithms...

Visual Data Structures Cheat Sheet — https://photonlines.substack.com/p/visual-data-structures-ch...

Re: Quicksort explained IKEA-style

#133

Post by [deleted] »

Dan42 wrote: post #14

This is cool, but missing a LOT of details between steps 4 and 5, which is the meat of the quicksort. Actually, the first and last elements of step 4 would be swapped, which means the order depicted in step 5 is incorrect.

[deleted]

Re: Quicksort explained IKEA-style

#134

Post by [deleted] »

hdjrudni wrote: post #77

I was confused by step (3). The right pillar doesn't need to move right because it's already to the right of the chosen pillar. I guess what it's trying to say is just "mark it as needing to be to the right", and then do the opposite in (4) and then (5) is where things actually move.

[deleted]

Re: Quicksort explained IKEA-style

#135

Post by crdrost »

xigoi wrote: post #99
crdrost wrote: post #82

Earlier quoted context omitted.

For me the key was just application to figuring out if any cards are missing in a deck by sorting it. Assume spades In your first pass, divide the deck into black and red cards. Then divide black into spades and clubs. Then divide spades into 7. Then insertion sort the cards 7, spades are now sorted. Clubs come next, divide into 7, insertion sort, and combine. Split diamonds and hearts, repeat with diamonds, repeat w…

What you’re describing is more like MSD radix sort.

So binary MSD radix sort is also just called "binary quicksort" by some authors; they are substantially the same algorithm. How can I explain?

If you really want to replicate the exact swaps and pivoting in the most common form of quicksort, what your fingers will actually do, looks like this.

1. Cut the to-be-sorted deck-portion in half so that you can peek at the first, last, and middle card. Choose the median and swap it to the back of the deck.

2. The deck now sits in your left hand and your right hand conceptually contains two empty stacks of cards, the one between thumb and forefinger is a stack pivot.

3. You are permitted two operations: (a) deal a card > pivot from the left hand onto the back of the second stack, or (b) deal a card 4. Process the whole left hand this way; at the end the pivot you selected will be at the back of the first stack in your right hand. Separate it out and recurse on the two remaining stacks.

So if you do this enough you'll start to appreciate these two things:

- "with cards I don't really need to rotate that second stack card by card whenever I add to that first stack -- that's not affecting correctness, it's just needed for array sorts to be in-place"

and similarly

- "with cards I sometimes get these really stupid starts where like the median is 10 of spades and I'm going to split this like 9-1-42, eff it I'm just going to pretend that the median was the king of clubs, that's what I needed to split the damn deck in half."

and those are the optimizations performed in the above description of quicksort.

Re: Quicksort explained IKEA-style

#136

Post by jerjerjer »

ozgung wrote: post #43

I’ve just completed reading all 8 posters on the site. For some reason I find them easier to understand than any written content, code or math. They are all intuitive. It was fun and engaging to solve their notation and meaning they want to convey. The one with AVL trees was the most useful to me.

Also checked the PDF compilation and it is a surprisingly effective way to explain algorithms considering there are no words at all.

Re: Quicksort explained IKEA-style

#137

Post by yifanl »

photon_lines wrote: post #131
ksenzee wrote: post #129

Earlier quoted context omitted.

If you’re an outlier, I’m out there with you: I’ve also been writing software professionally for 20 years, I have no CS degree, and I’m not fool enough to reimplement algorithms like quicksort that are sitting right there in stdlib. I similarly found this explanation a lot more useful than anything else I have read about quicksort, and I’m confident I could implement it now, but couldn’t have before I read this.

If you guys like visual-explanations that are a bit more intuitive -- I put actually made guides on both data-structures and algorithms not too long ago which you can find here: Visual-Focused Algorithms Cheat Sheet — https://photonlines.substack.com/p/visual-focused-algorithms... Visual Data Structures Cheat Sheet — https://photonlines.substack.com/p/visual-data-structures-ch...

The Fenwick tree in your cheat sheet seems a little broken

Re: Quicksort explained IKEA-style

#138

Post by flexagoon »

TeMPOraL wrote: post #45
klibertp wrote: post #8

If I didn't know how quicksort works - and I had to learn, since for some reason in FP languages quicksort is typically next after "hello world" - I would struggle to make sense of the pictures, I think. However, it's absolutely brilliant as a memory refresher: it packs so much info in so little space that it's insanely efficient. I imagine it would pair well with a good textbook on algorithms.

> for some reason in FP languages quicksort is typically next after "hello world" Because the recursive implementation is surprisingly straightforward and concise, and more-less demonstrates what the whole paradigm is about. As much as I hate to admit it, it's a good learning artifact.

> Because the recursive implementation is surprisingly straightforward and concise

It's also technically not quicksort

Re: Quicksort explained IKEA-style

#139

Post by photon_lines »

yifanl wrote: post #137
photon_lines wrote: post #131

Earlier quoted context omitted.

If you guys like visual-explanations that are a bit more intuitive -- I put actually made guides on both data-structures and algorithms not too long ago which you can find here: Visual-Focused Algorithms Cheat Sheet — https://photonlines.substack.com/p/visual-focused-algorithms... Visual Data Structures Cheat Sheet — https://photonlines.substack.com/p/visual-data-structures-ch...

The Fenwick tree in your cheat sheet seems a little broken

Can you go into a little more detail? What is broken exactly?

Re: Quicksort explained IKEA-style

#140

Post by yifanl »

photon_lines wrote: post #139
yifanl wrote: post #137

Earlier quoted context omitted.

The Fenwick tree in your cheat sheet seems a little broken

Can you go into a little more detail? What is broken exactly?

The visual is extremely hard to understand how it relates to the description, given that it looks to be 1-indexed, but the description only makes sense for 0-indexing (4th element stores the sum of the first 4 elements), not to mention none of the binary indexes seem to be storing the correct sums (or they're storing sums of a tree that isn't being presented).
Post reply on HN