ScratchData LogoScratchData
Back to _youtubeN1's profile

Skew Binary Smoothsort vs. Heapsort vs. JSort

_Y_youtubeN1•Created January 11, 2018
Skew Binary Smoothsort vs. Heapsort vs. JSort
1
0
74 views
View on Scratch

Description

Skew binary smoothsort: - construct a forest of perfect binary trees, with the depth of consecutive nodes spread out in a fashion similar to 2-adic numbers (contrast to heapsort, which clumps all nodes of equal depth together) - turn the forest into a proper heap by sifting nodes down in a bottom-up fashion -repeatedly move largest root to end, delete (disregard) it from heap, restore heap property -alternatively, the building of the heap can also be thought of as iteratively merging the binary trees of increasing order, with special gaps between them (due to the def'n that every binary tree has a single root node at the end of it) adaptive for nearly sorted lists Heapsort: https://en.wikipedia.org/wiki/Heapsort simple heap indexing, sorting time for any list of fixed size stays relatively constant Jsort: - build a min-binary-heap, with root being first item in list - build max-heap from resulting list, now with root being last item - another way is to do min-heap, reverse the resulting list, and build a max-heap with root as first item, then reverse again; uses same index systems for parent/child - insertion sort final result

Project Details

Project ID197402389
CreatedJanuary 11, 2018
Last ModifiedJanuary 16, 2018
SharedJanuary 13, 2018
Visibilityvisible
CommentsAllowed