|
Amazon Polly audio version of this post
|
So I was bored and watching videos, and I discovered these wonderful videos about the sounds of sorting.
I was intrigued by how fast the Gravity sort seemed to be, and others in the comments were as well. It seems to be one of the fastest in the video at about 11 seconds.
Most of the other sorts take 20 seconds or more.
So I wanted to try to implement the sort in C# to see what it can do. The fruits of that labour are here:
https://github.com/eanbowman/GravityBeadSortDemo/
Not as pretty as the colour circle or the other visualizations in the sound of sorting project, but it does the trick.
Maybe some day in the distant future I’ll add visualizations, or you can fork the code and make some for yourself!
The relevant sort code is as follows:
public static void BeadSort(ref int[] data)
{
int i, j, max, sum;
byte[] beads;
for (i = 1, max = data[0]; i < data.Length; ++i) if (data[i] > max)
max = data[i];
beads = new byte[max * data.Length];
for (i = 0; i < data.Length; ++i)
for (j = 0; j < data[i]; ++j)
beads[i * max + j] = 1;
for (j = 0; j < max; ++j)
{
for (sum = i = 0; i < data.Length; ++i)
{
sum += beads[i * max + j];
beads[i * max + j] = 0;
}
for (i = data.Length - sum; i < data.Length; ++i)
beads[i * max + j] = 1;
}
for (i = 0; i < data.Length; ++i)
{
for (j = 0; j < max && Convert.ToBoolean(beads[i * max + j]); ++j);
data[i] = j;
}
}
