r/coding • • Sep 21 '20

I Created a Visualization of 20 Sorting Algorithms with Java. Which one do you like most?

https://www.youtube.com/watch?v=AVt0lAklAtM

[removed] — view removed post

157 Upvotes

30 comments sorted by

5

u/compilerstuck Sep 21 '20

Hey yall!

This is my Try on writing a Visualizer for Sorting Algorithms. I am currently doing a series of this, trying to find new ways to Visualize these. My last one was a 3D Spinning Cube.

This series will continue on my YT Channel.

Let me know what i could improve below :)

0

u/[deleted] Sep 22 '20

[deleted]

1

u/compilerstuck Sep 22 '20

Good idea. Might do it in the future!

4

u/mad_edge Sep 21 '20

Woah! How did you make the sound??

5

u/compilerstuck Sep 21 '20 edited Sep 21 '20

I used a Midi Synth to play sounds according to the elements in the array beeing moved

2

u/Ashed-23 Sep 21 '20

Amazing work! I enjoyed it.

2

u/Just_Some_Random_Boi Sep 22 '20

My boyfriend just sent this to me.

He knows how much I get hypnotized by sorting algorithm videos. He knows I now must watch it all the way through.

THIS IS FOR YOU, CLARENCE

2

u/compilerstuck Sep 22 '20

Haha, you're welcome ^

2

u/Mihir45 Sep 22 '20

Great work man!

1

u/compilerstuck Sep 22 '20

Thank you <3

4

u/[deleted] Sep 21 '20

No Bogo Sort? Disappointing

7

u/slapnuttz Sep 21 '20

It’s still rendering lol

2

u/nizzasty Sep 22 '20

haha dots go brrrrr

1

u/[deleted] Sep 22 '20 edited Nov 10 '24

simplistic brave jar reply wild ancient adjoining flowery cautious coordinated

This post was mass deleted and anonymized with Redact

1

u/recycled_ideas Sep 22 '20

The problem with what we know, or more accurately what we think we know about algorithms is that big O notation is highly abstracted from hardware.

We all "know" that an array insertion is an O(n) operation because you've got to move every element after the insertion individually.

The thing is, in hardware, that's not how it works.

Over the years, we've discovered that accessing and moving contiguous blocks of memory around quickly is really common and really useful so we've built functionality to do that really efficiently.

So an array insertion is, in actuality done in constant time in most circumstances.

This is why despite what you learned in your data structures class almost every collection you'll encounter in real code is array based. Because the biggest drawback of an array is insertion time is O(n) and that's not true.

Algorithmically insertion sort and bubble sort are actually the same, best case n, average and average and worst n2, but bubble sort works in a way that interacts well with hardware. Lots of contiguous memory access.

Bubble is actually not particularly bad, especially given how incredibly simple it is to write. Heap sort is better, but bubble isn't actually that bad.

The big place where bubble (and heap) fall down is when you can allocate multiple threads to the sort, because bubble is not parallel.

1

u/Isvara Sep 22 '20

So an array insertion is, in actuality done in constant time in most circumstances.

Can anyone confirm this? If so, how?

1

u/recycled_ideas Sep 22 '20 edited Sep 22 '20

Basically your hardware can move large blocks of continuguous memory in a single operation, this applies at all levels, cache, memory, disk, it's all built to rapidly move large blocks around at once.

It's not exactly constant time, it's really n divided by a really large number, but for most uses it scales things down so much that it may as well be.

For the scale of this video an insertion is constant time.

Edit: More importantly any access that isn't contiguous will be a large number slower as well.

1

u/Isvara Sep 22 '20

Are you talking about DMA?

in a single operation

That doesn't mean in constant time.

it's really n divided by a really large number

That's still O(n).

1

u/recycled_ideas Sep 22 '20

That doesn't mean in constant time.

O(1) is constant time.

That's still O(n).

Again, you're missing the limitations of big O notation.

Big O notation is an abstraction applied at every scale.

So 1,000,000n is the same as n, because for sufficiently large numbers it doesn't matter.

But in reality a million times your array length is massively slower than 1 times the length for almost all use cases.

Thus length divided by a really large number is still O(n), but in reality, it's a lot smaller than N.

Then you factor in the fact that the CPU can only see a small amount of memory at a time and that these moves aren't actually being done in the CPU.

So while the controller might be doing a thousand operations, so long as it can stay at least one operation ahead of the CPU, which it can, it may as well have been a single operation, because the data you need is always ready when you need it.

So effectively, from the CPUs perspective, that allocation is O(1) it does one operation and it's all magically done.

Because again big O notation is an abstraction from an era where CPU, memory and disk were all basically the same speed or close enough and everything was controlled by the CPU.

That's not how modern computers work.

1

u/Isvara Sep 22 '20

O(1) is constant time.

I didn't say O(1), I said single operation (quoting you, in fact).

So 1,000,000n is the same as n, because for sufficiently large numbers it doesn't matter.

Yes. I already pointed out that constants don't matter.

It's not about how long something actually takes. It's about the rate at which that time grows with respect to the input.

these moves aren't actually being done in the CPU.

So while the controller might be doing a thousand operations

So are you talking about DMA or not?

There's definitely no magic involved, and moving chunks of memory around isn't O(1).

1

u/recycled_ideas Sep 22 '20

It's not about how long something actually takes. It's about the rate at which that time grows with respect to the input.

No, it doesn't, which is the point I'm trying to make.

Big O notation doesn't measure that at all, because what Big O notation measures is not what hardware does. Big O measures an abstraction of complexity and not a particularly good abstraction of complexity.

The two things are not the same.

A linked list insertion is canonically O(1), but if the pointer you're updating has been paged to disk it's still going to take forever.

We're also talking about what your performance will be in general usage, and in general usage, array insertion is much faster than the theory says it should be.

There's definitely no magic involved, and moving chunks of memory around isn't O(1).

By magic I don't mean literal magic, I mean that your core isn't going to sit there churning through single allocation moves for the entire array, it's going to be able to keep on going.

The question was why is bubble sort faster than insertion, the answer is that at this scale, and at most scales, bubble sort is much faster than it should be and it's already as fast as insertion complexity wise.

1

u/Isvara Sep 22 '20

The question was why is bubble sort faster than insertion, the answer is that at this scale, and at most scales, bubble sort is much faster than it should be and it's already as fast as insertion complexity wise.

I'm pretty sure the answer was that there's a bug in the measurement code.

1

u/recycled_ideas Sep 22 '20

Insertion sort and Bubble sort are both the same complexity, they scale the same way, but bubble benefits more from hardware.

We're not talking about an O(n) vs O( n2). There's no reason bubble should be slower in the first place.

1

u/[deleted] Sep 26 '20 edited Nov 10 '24

grey profit plucky bright pathetic worry correct growth dime carpenter

This post was mass deleted and anonymized with Redact

1

u/recycled_ideas Sep 26 '20

Bubble and insertion sort have the same big O. Both are O(n) in the best case and O( n2) for worst and average case for the algorithm.

However, nominally speaking an array insertion in and of itself is, nominally O(n) as well, which as I'm thinking about it is irrelevant to a bubble sort, so I'm not sure what I was thinking before.

1

u/[deleted] Sep 26 '20 edited Nov 11 '24

hungry subsequent encouraging party berserk zonked lock future unite attempt

This post was mass deleted and anonymized with Redact