Add an option to relax the success condition to yielding a heap.

bertdobbelaere / SorterHunter

An evolutionary approach to find small and low latency sorting networks

MIT License

55 stars 4 forks source link

Add an option to relax the success condition to yielding a heap. #13

Open sh1boot opened 5 months ago

sh1boot commented 5 months ago

I was just wondering if make_heap() could benefit from implementation as a sorting network in some cases, as the preamble to various other algorithms adjacent to sorting.

So I guess the first thing to know is how much smaller and shorter the network can be compared to a full sort. Is that a thing worth implementing?

Seems like a thing I should just try for myself, but I'm halfway down a whole other rabbit hole right now and I just wanted to get this written down before I forgot.

bertdobbelaere commented 2 weeks ago

I think that creating a heap of n elements could be done with a trivial network of n-1 elements. In pseudocode: for k from n-1 downto 1: add_element(k, floor((k-1)/2)) e.g. for n=10 you get the network (9,4),(8,3),(7,3),(6,2),(5,2),(4,1),(3,1),(2,0),(1,0) The output is now a heap, and it is optimal because with less elements (n-2) the network is no longer connected. So actually the network is just another representation of what make_heap() already does.