jgamble / algorithm-networksort Goto Github PK

As the subject says. Examples need improvement, and there's leftover text from the non-object oriented version.

I'm apologise, this is more question than actual issue report.
but, is there any known efficient sorting networks or algorithms, which leave equal elements in its original order ? except obvious bubble sort.

if yes, is it possible to include them in this project ?

PS: thank you for your work and researches.

... as described in chapter 5 of Designing Sorting Networks.

I have a name question: should I include the 'Van' when making a key out of his name? Right now the key is 'voorhis16', and I'm wondering if it should be 'vanvoorhis16'. I am very ignorant of naming conventions, unfortunately.

Likewise, Worldcat has the surname of the author of Designing Sorting Networks as Baddar, not Al-Haj Baddar, so I'm going to change her entry keys to 'baddar##'.

If I'm being an idiot in one or more respects, please let me know..

https://arxiv.org/pdf/2002.05599.pdf

Sorry I'm using this issue tracker as a place to dump cool links; maybe we should make some kind of wiki page?

Anyway see appendix S in the following paper: https://ntruprime.cr.yp.to/ntruprime-20170816.pdf

It describes a vectorised implementation of an n=32 merge-exchange net used for constant-time sorting. I have some more info on constant time applications in slides 31-33 of my (now pretty dated) presentation:

https://hoytech.github.io/sorting-networks/#slide31

Right now a single radius value is used for the endpoints of both comparator and input lines. But the Knuth diagrams in The Art of Computer Programming have, for example, circles on the comparator lines, but not the input lines.

There need to be two radius keys ('compradius' and 'inputradus') to let users mimic the style of TAoCP.

The "Best" algorithm could be split into two different categories: "Best size networks" (the current "Best") and "Best depth networks". While these networks are more or less the same for the small sorting networks, the best size-optimal and depth-optimal networks that we currently know for sizes > 16 are not always the same. For example, the paper Sorting Networks: to the End and Back Again by Codish & al. presents new sorting networks for sizes 17, 18, 19 and 20 whose depth is better than the ones we knew (and prove the resulting sorting network 17 to actually be depth-optimal).

Size-optimality and depth-optimality are interesting in different contexts, so providing both could be interesting for users, depending on what they need their sorting networks for.

Much of the code would be simplified if the network was changed into an object, particularly the code that counts comparisons and comparators-in-parallel.

As discussed in #8, 23 and 24 -input networks

Postscript code from version 2.01 is not parsing. I'll have to check, but I don't believe there's been a change from the initial version that had a postscript output, so it may be that the postscript parsers I used to check the output back then were more lax.

Regardless, this needs fixing.

Just continuing my habit of abusing this issue tracker by dropping interesting articles :)

https://jix.one/proving-50-year-old-sorting-networks-optimal-part-1/ by @jix on github: https://github.com/jix/sortnetopt

Relevant to this repo, I like how he drew the "rounded brackets". My way of doing this was a total hack, that I have now in fact lost, but here was the output: https://hoytech.github.io/sorting-networks/#slide25

I think we're at a satisfactory point with the code. That leaves the documentation, which could stand improvement beyond the updated lists.

The exported functions from Algorithm::Networksort

• nwsrt()
• nwsrt_algorithms()

The exported functions from Algorithm::Networksort::Best

• nwsrt_best()
• nwsrt_best_names()
• nwsrt_best_title()

Yeah... I didn't consider what I was doing as far as consistency goes at all.

The plan: In Algorithm::Networksort, add an nwsrt_title() function, and rename nwsrt_algorithms() to nwsrt_names().

cc @hoytech because although I don't think enough days have gone by to catch people with this, you might be the exception.

If we add a shell sort implementation I think we'll have pretty much all the "classic" algorithms covered.

I think I have a print-out of Pratt's Shellsort and Sorting Networks somewhere, I'll see if I can dig it up and send a pull request...

Specifically the graph_*() methods and the helper functions.

More size-optimal sorting networks have been discovered recently thanks to several research projects (well, not size-optimal per se, but as optimal as we could find). The paper Using Symmetry and Evolutionary Search to Minimize Sorting Networks by Valsalam and Miikkulainen provides sorting networks using less compare-exchange units for sizes 17, 18, 19, 20, 21, 22 and 23 (even though the one of size 23 isn't better than sorting both halves of the array with the sorting networks of sizes 12 and 11 then using a Batcher's merge network to merge the two sorted halves).

I think that the "Best" algorithm could be extended to provide the best known size-optimal networks until size 32.

Just adding a ticket to point to this post, which may have another algorithm we could implement:

https://rjlipton.wordpress.com/2014/04/24/galactic-sortning-networks/

I haven't had a chance to look at it in detail.

The best.t test really slows down the CPAN installation.

I wonder if it's possible to do a "quick sanity check" that does a small sub-set of a full zero-one test unless the AUTHOR_TESTING environment variable is set, similar to how abecedarian.t works.

Hi :)

Some guy (Bert Dobbelaere) recently found new sorting networks with better size and/or depth than the ones in the current litterature. You should check out his project. There's also an extensive list of "best" sorting network that you might want to use to complete your library; you might also want to follow the project ince it is updated from time to time.

Cheers.