4 ms·

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 p

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)?

brudgers 10y ago
To me, I think that the space savings is exactly what should be emphasized to beginners. I love functional programming as much as the next person...well maybe almost as much...but quicksort without mutation is not quicksort. Showing beginners quicksort with mutation pulls back the curtain on functional programming and reveals the wizard. Functional programming, so long as we have Von Neumann machines, is a layer of abstraction and who am I to argue with Abelson and the Sussmans that beginning programmers should be introduced to abstraction layers as quickly as possible?
liamondrop 10y ago
Absolutely: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html https://www.cs.usfca.edu/~galles/visualization/ComparisonSor...
Asooka 10y ago
With so few elements, I think you can perform the in-place swap as one animation. Take the pivot out, put an arrow on the first and last elements in the list, then - if the left arrow points to an element greater than the pivot, swap the elements under the arrows and move the right arrow one cell left - else if the right arrow points to an element less than the pivot, swap the elements under the arrows and move the left arrow one cell right - else if one of the arrows points at the pivot, move the other arrow towards it until the two arrows point at the same cell, which now contains the pivot. You could show the full selection animation the first time and then just move all elements to their final places at once every subsequent time. I would also replace the random pivot selection with selecting the middle-valued element among the first, middle and last element of the array.
bjarnagin 10y ago
Nice work! One other note, in addition to the comments here: the algorithm as it's currently written will drop repeated elements. You can easily fix that by changing `greater` to filter elements greater than or equal to the pivot.

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)?

brudgers 10y ago

To me, I think that the space savings is exactly what should be emphasized to beginners. I love functional programming as much as the next person...well maybe almost as much...but quicksort without mutation is not quicksort. Showing beginners quicksort with mutation pulls back the curtain on functional programming and reveals the wizard. Functional programming, so long as we have Von Neumann machines, is a layer of abstraction and who am I to argue with Abelson and the Sussmans that beginning programmers should be introduced to abstraction layers as quickly as possible?

liamondrop 10y ago

Absolutely: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html https://www.cs.usfca.edu/~galles/visualization/ComparisonSor...

Asooka 10y ago

With so few elements, I think you can perform the in-place swap as one animation. Take the pivot out, put an arrow on the first and last elements in the list, then - if the left arrow points to an element greater than the pivot, swap the elements under the arrows and move the right arrow one cell left - else if the right arrow points to an element less than the pivot, swap the elements under the arrows and move the left arrow one cell right - else if one of the arrows points at the pivot, move the other arrow towards it until the two arrows point at the same cell, which now contains the pivot. You could show the full selection animation the first time and then just move all elements to their final places at once every subsequent time. I would also replace the random pivot selection with selecting the middle-valued element among the first, middle and last element of the array.

bjarnagin 10y ago

Nice work! One other note, in addition to the comments here: the algorithm as it's currently written will drop repeated elements. You can easily fix that by changing `greater` to filter elements greater than or equal to the pivot.