Show HN: Illustrated Quicksort algorithm

[bogomipz]

This is neat. If you enjoyed this you might also like the Hungarian folk dancers demonstrating sorting algorithms on youube:

https://www.youtube.com/watch?v=ywWBy6J5gz8

[Cyph0n]

That was simply amazing.

[kstirman]

Damn it, you beat me to it. ;-)

[skidding]

Hi. This is my 2nd algoritm visualization. Creating them is fun.

Besides designing the illustrations, I've spent a lot of time crafting the framework so expect more of these in the future. Ongoing effort, but also tried to make the codebase approachable for others to learn from and be able to contribute: https://github.com/skidding/illustrated-algorithms

How would you make algorithms fun? Looking forward to ideas and feedback. Thanks!

[deanclatworthy]

Looks great. Have an option to slow it down though. I couldn't follow the animation and the code on the right it was going so quickly.

[lanna]

some constructive feedback: one of the greatest features of quicksort is that it is an in-place algorithm, it doesn't use any additional storage. qsort cleverest trick is to switch an element greater than the pivot with one smaller in a single step, and all of that is lost in the animation when the first thing it does is to group the fruits into the "less" and "greater" piles. as it is, your animation is great, but it doesn't really illustrate qsort, especially the most fundamental aspects that set it apart from other sorting algorithms.

[bastijn]

I agree. I find https://visualgo.net/sorting to provide easier to understand animations. Also, the fruits are less understandable to me than simple numbers.

[imh]

It depends on whether pedagogy is the primary goal. For teaching, the in-place implementation can come after the conceptual "pick a pivot, partition accordingly, then recurse" is made concrete.

[skidding]

Good points. I'll think about this and read more on Quicksort.

Do you think these aspects can be incorporated without adding extra baggage for beginners (the primary target for this visualizations)?

[baby]

I was watching this: https://www.youtube.com/watch?v=ywWBy6J5gz8 and wondering why it was different from this post's animation.

[skidding]

Update: I realize the featured example is not the most optimal Quicksort implementation. I doesn't even handle duplicates. Indeed this variant was chosen primarely because of its aesthetics.

While I'd like to keep the mission of this project to "illustrating the basic mechanics of algorithms as elegantly as possible", I realize this can be a) annoying for people who understand the specifics in depth, and b) not enough (or confusing) for people just picking this up. Which is why I'm thinking of creating an info page for each algorithm to:

  - Outline the limitations of the featured version
  - List a number of possible improvements (e.g. pivot strategies)
  - Link to external resources for complete examples & docs

Open discussion. What do you think?

[UweSchmidt]

Reminds me of some of my own side projects: great vision, massive effort, but then it just might not be 100% on point / what "the market" needs. You've accomplished a lot - as you know finishing any project is not easy at all and this one has quite a few clever and unique ideas in it!

Best thing imo is the idea to go forward and backward through code and see the results live. I'd love to have this to study or debug code, and to really see and understand the magic of some operations in a visualization like this.

The thing is, algorithms like Quicksort are quite involved. In order to understand I'd need at least 2 intermediate steps between the animation and the code:

- The core concepts, like "recursion, in place sorting, complexity/performance average/worst case, trouble when list already sorted" etc.

- The programming ideas, like "we pick a pivot, we use a random element from the list but you could use any", "our recursion stops when there is only 1 item in the sub-list" etc.

If these things were linked to a) the animation and b) the code and I could experience it all at once, that would be amazing (but a lot of work for you of course :-))

Also: - I kept sorting the fruits by size somehow, and due to the language barrier a "P"ineapple would be an "A"nanas for me - If I commit to learning something I like to go to a place that has comprehensive information, even if various places to one thing well. - Preventing zoom and the scrolling code is not ideal imo. - Code could be simpler and clearer. - Maybe the task to explain Quicksort like this is just too huge

[snackai]

Personally I find https://visualgo.net/ to be more helpful. I don't think the fruits are too intuitive.

[skidding]

visualgo.net is a great resource for understanding algorithms indeed, I wouldn't dare try to compete.

I intended to compare objects of different heights at first, but ended up reusing the emoji tiles from Binary Search to reduce implementation time. I'll try to get more creative with the next (e.g. a maze for BFS).

[Rabei]

Good work, looks great!

I have the following comments, hope you find them useful: * I find counter intuitive that the animation goes up, i think it should go down, but that probably just me. * Would recommend using something different than fruit which is probably one of the last things that comes to mind when thinking of ordered sets, also the picture keeps getting in the way of me sorting lexicographically in my mind. * A per step mode would also come in handy.

[skidding]

Appreciate the feedback!

[blinry]

If you enjoy visual or interactive explanations, we're currently building a community for that on Reddit: https://www.reddit.com/r/explorables/

[skidding]

Update 2: I've taken action to try to alleviate some of the confusion and integrate the helpful feedback you've sent me.

  - Added Disclaimer to clarify the project mission and limitations
  - Created Footnotes section for insights collected from the community

Both can be found here: https://github.com/skidding/illustrated-algorithms/blob/mast...

Thanks!

[kbr]

Hey, love it! I know that you know it can handle duplicates, but a simple fix can work here.

Make an array called `equal` before making the `less` and `greater` arrays.

  const equal = arr.filter(i => i === pivot);

Then, instead of adding the pivot, add the equal array.

  return [
    ...quicksort(less),
    ...equal,
    ...quicksort(greater)
  ]

[notduncansmith]

This was cool, the highlighted code tour is a great touch.

For anyone else who enjoyed this, you might also enjoy this blog post full of animated algorithms by Mike Bostock: https://bost.ocks.org/mike/algorithms/

[baby]

That's amazing. Just two questions

1) on quicksort:

    const less = list.filter(i => i < pivot);
    const greater = list.filter(i => i > pivot);
  

Wouldn't this be faster:

    less    = what's < pivot
    greater = the rest

2) What is the algorithm people use?

[cmurphycode]

I may not have parsed your question correctly, so I apologize in advance. Assuming you are asking about what happens to the "equal" elements-

Yes, there is a bug in this code. It doesn't handle repeated elements.

If you fix the code by including an equality in one of the two groups, then it works, but it degrades when there are many repeated elements. In the worst case, you can only shrink your groups by one each time, which means the complexity changes to O(n^2) :(

You can fix THIS issue using a 3-way partition. That is the algorithm I've used. With a good pivot choice (random or median of three), this gives you an in-place sort which is guaranteed to be O(nlgn). Nice!

[skidding]

1) It's written in a functional way where you don't mutate the initial list. Edit: I guess you could iterate once and populate both left and right sides at the same time, but that would make the code more verbose (personal bias).

2) What do you mean?

[gigatexal]

Thank you for this. The work to both understand the algorithm and then animate it, much appreciated

[vinylkey]

That's snazzy, good work!

I found myself wanting to set my own initial order of the list to see what some specific edge cases (already sorted, one element off from being sorted, in reverse order, etc) look like.

[hellofunk]

There was another interesting animated sorting page I found on here many months ago. I haven't seen it in the comments yet and I can't find it anywhere, but this stuff is cool.

[shric]

This one? https://www.toptal.com/developers/sorting-algorithms

[amelius]

Why do people keep using Quicksort as an example?

I find Mergesort to be much more intuitive. And better yet, it has a much better worst-case performance.

[brudgers]

A lot of things get called 'quicksort' that are not as quick as Hoare's original algorithm. Pragmatically, it was quick compared to Von Neumann's merge sort.

Sure both are time O{n log n}. Sure both are space O{n}. But merge sort is ~2n + c space and quicksort is n + c space. In the days when computers had kilobytes of memory and rooms full of tape drives, the memory efficiency of quicksort made it much quicker.

Which brings up the difference between mathematical worst case performance and engineering worst case performance. Statistically, the use of a random pivot (which was part of Hoare's paper) gives quicksort similar worst case performance to merge sort. In production with 'big data', hitting slow secondary memory such as persistent storage will dominate throughput.

[gpderetta]

I like merge sort, but quick sort is also very elegant.

[skidding]

Illustrating both seems most advantageous then :)