Nibble Sort

#1

Post by caf » Tue, Jul 21, 2015, 6:52 AM UTC

Re: Nibble Sort

#2

Post by serkanyersen » Tue, Jul 21, 2015, 7:49 AM UTC

This kind of blog posts are super interesting and depressing at the same time :) makes me question my programing skills. Almost all of the things mentioned here are over my head.

Thanks for sharing though, very interesting

Re: Nibble Sort

#3

Post by amelius » Tue, Jul 21, 2015, 7:59 AM UTC

How does it scale?

Re: Nibble Sort

#4

Post by ploxiln » Tue, Jul 21, 2015, 8:19 AM UTC

amelius wrote: post #3

How does it scale?

These solutions do not scale at all. Even with tweaks, they could not sort 18 nibbles (or 32 nibbles). But they are very interesting, and these kinds of tricks do find some practical use in things like video codecs.

Re: Nibble Sort

#5

Post by userbinator » Tue, Jul 21, 2015, 8:28 AM UTC

Upon seeing the description of the problem, my first thought was "use a sorting network" too, although I'd probably try to use fewer registers...

Re: Nibble Sort

#6

Post by signa11 » Tue, Jul 21, 2015, 8:30 AM UTC

amelius wrote: post #3

How does it scale?

> How does it scale?

what do you mean ? the task asks to sort 4bit nibbles in 64bit words, so you optimize for that problem space...

Re: Nibble Sort

#7

Post by iso8859-1 » Tue, Jul 21, 2015, 8:32 AM UTC

I have a short Python script to generate sorting networks (and diagrams like the one found in the post): https://github.com/ysangkok/python-sorting-networks/blob/mas...

I was a bit disappointed to see no code in this blog post for the algorithms used to generating the pairs. Is there are templated C++ library for this?

Re: Nibble Sort

#8

Post by jcr » Tue, Jul 21, 2015, 10:02 AM UTC

The hanshq.net story is just one of three blog entries that John Regehr linked to yesterday:

http://blog.regehr.org/archives/1242

The other two are:

http://jbeekman.nl/blog/2015/01/nibble-sort/

http://belkadan.com/blog/2015/05/Nibblesort/

Re: Nibble Sort

#9

Post by simi_ » Tue, Jul 21, 2015, 11:16 AM UTC

serkanyersen wrote: post #2

This kind of blog posts are super interesting and depressing at the same time :) makes me question my programing skills. Almost all of the things mentioned here are over my head. Thanks for sharing though, very interesting

There's an ongoing Algorithms course on Coursera right now!

https://www.coursera.org/course/algs4partI

edit: found another one, also happening now (can't believe I missed it): https://www.coursera.org/course/algo

Re: Nibble Sort

#10

Post by nly » Tue, Jul 21, 2015, 12:16 PM UTC

serkanyersen wrote: post #2

This kind of blog posts are super interesting and depressing at the same time :) makes me question my programing skills. Almost all of the things mentioned here are over my head. Thanks for sharing though, very interesting

Sometimes programming feels like: "Interesting work, useful work. Pick one". People who get to do both are privileged indeed, the rest of us sit around feeling either bored or useless.

I'm thankful at least, in contrast to several friends who suffer from depression and are not prone to nerd sniping, that, for me, these two states are almost mutually exclusive.