w0rthy / ArrayVisualizer

Sorting Visualizer with 6 different views and 14 included sorting algorithms
MIT License
521 stars 123 forks source link

Interesting research into your "disparity circle" formula along with a new, smoother one #22

Open MusicTheorist opened 4 years ago

MusicTheorist commented 4 years ago

I was chatting in my Discord with Aphitorite on GitHub, and they actually dug into your "disparity curve" formula a bit. Some interesting stuff was discovered, and we wanted to share it with you!

So first of all, we were talking about my modified version of your formula from my fork that's able to handle arbitrary array lengths, which is the following:

double len = ((ArrayVisualizer.getCurrentLength() / 2d) - Math.min(Math.min(Math.abs(i - array[i]), Math.abs(i - array[i] + ArrayVisualizer.getCurrentLength())), Math.abs(i - array[i] - ArrayVisualizer.getCurrentLength()))) / (ArrayVisualizer.getCurrentLength() / 2d);

Yeah, I know... I didn't refactor it after changing it around, and the line of code it takes up is an absolute mess. But it turns out that you had written up a partial triangle wave function (without using trig functions)!

https://cdn.discordapp.com/attachments/592103638034415647/733325936417570926/SharedScreenshot.jpg

That's why the peaks of the disparity circle visual are always jagged! You can especially see that here:

Your original formula: https://cdn.discordapp.com/attachments/592103638034415647/733197874434932807/Screenshot_516.png

versus Aphitorite's new cosine wave formula: https://cdn.discordapp.com/attachments/592103638034415647/733197892264656946/Screenshot_515.png

Their new cosine wave formula is as follows:

double len = (1 + Math.cos((Math.PI * (array[i] - i)) / (ArrayVisualizer.getCurrentLength() * 0.5))) * 0.5;

I personally found this super fascinating; hope this was interesting for you too!

MusicTheorist commented 4 years ago

Update: Aphitorite cleaned up the original formula (triangle wave) as well...

double len = 2 * Math.abs(Math.abs(array[i] - i) - ArrayVisualizer.getCurrentLength() * 0.5) / ArrayVisualizer.getCurrentLength();