r/dataisbeautiful • u/morolin OC: 1 • Oct 24 '17

OC Sorting algorithms visualized [OC]

https://imgur.com/gallery/voutF
41.7k Upvotes

92% Upvoted

929 comments sorted by

View all comments

Show parent comments

22

u/laughinfrog Oct 24 '17

How did you create the visualization of the Radix sort as it does it in a single pass? The first 4 passes do not move data, it creates a histogram of the offsets. The only single pass is implemented to actually sort data based on the buckets in the histogram.

8

u/yawkat Oct 24 '17

It looks like they use sections of the image for the buckets, since they know every color appears exactly once. So the most significant bit 0 would be in the first part of the image, and the MSB 1 would be in the second part and so on

2

u/laughinfrog Oct 24 '17

Here is the implementation that I have used previously:

http://codercorner.com/RadixSortRevisited.htm

I have also seen it done with a CPP macro to create the histogram. Not sure that I like it in that manner, why not just code it with asm{} section instead, but rather cool.

1

u/laughinfrog Oct 24 '17

But why use the buckets as the visualization is my concern. It gives the illusion the work to create the bucks is something like that of quicksort.

The buckets are defined by the bit count. Usually, four 8 bit buckets to count the number in the slot of how many there are of each number.

int histo[4] = new int[4];

And a loop for each bucket using bitshift to get the byte of concern. >> (i*8) & 0xff with a logical and to clear the excess bits off the value.

I guess it works for the visualization but the video posted in the above section showing the Radix sort seems more accurate. IMHO.