ArrayVisualizer icon indicating copy to clipboard operation
ArrayVisualizer copied to clipboard

Refactor Heap Sorts to use Writes instead of Swaps

Open aphitorite opened this issue 4 years ago • 2 comments

Similar case that separates Optimized Gnome from Insertion. The total amount of writes can be halved by inserting the item down the heap instead of swapping.

Changed: Max Heap Min Heap Flipped Min Heap Ternary Heap

Unchanged: Weak Heap - makes the implementation a lot less intuitive Poplar Heap - doesn't directly improve the sort

aphitorite avatar Jun 15 '20 19:06 aphitorite

this looks good to me, and i think something similar could be applied to other selection sorts as well. the issue is, do we change the workings of the existing sorts, or add them as separate optimized versions? i assume that @MusicTheorist would prefer the latter, since that's why Flipped Min Heapsort exists as a separate algorithm to Min Heapsort in the first place

landfillbaby avatar Jul 21 '20 19:07 landfillbaby

I would prefer a separate "optimized" version, yeah! Remember that we're going to better organize the sort/shuffle/distribution lists later on to cut down on the clutter!

MusicTheorist avatar Jul 21 '20 19:07 MusicTheorist