News for hackers. Stuff that matters.
Re:Is this the simplest (and most surprising) sorting algori... by smusamashah on Tuesday October 05, 2021 @09:50AM (#28759471)
This is how it looks like https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...

It behaves more like insertion sort.

Re:Is this the simplest (and most surprising) sorting algori... by edflsafoiewq on Tuesday October 05, 2021 @10:29AM (#28759972)
Break the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps.

  for i = 1 to n do
    - Inserts A[i] into A[1 to i-1], using the A[i]
    - spot as a temp variable.
    for j = 1 to i-1 do
      if A[i] < A[j] then
        swap A[i] and A[j]

    - Does nothing.
    for j = i do
      if A[i] < A[j] then
        swap A[i] and A[j]

    - Permutes A[i to n], placing the maximum into
    - A[i]. Since A[i] already has the max after the
    - first iteration, it won't change, and we don't
    - care how A[i+1 to n] is permuted since it gets
    - sorted anyway.
    for j = i+1 to n do
      if A[i] < A[j] then
        swap A[i] and A[j]
Re:Is this the simplest (and most surprising) sorting algori... by Izkata on Tuesday October 05, 2021 @10:59AM (#28760385)
And if you start the inner loop at "j=i" and flip the comparison order, it turns into something very similar to a very slow selection sort.
Re:Is this the simplest (and most surprising) sorting algori... by chubot on Tuesday October 05, 2021 @01:21PM (#28762465)
Wow this page is very cool! I recommend clicking these four boxes:

    - quick sort
    - merge sort
    - custom sort (this naive algorithm)
    - bubble sort
Then click “start”.

And then you can clearly see the difference side by side, including the speed of the sort!

Quick sort is quick! Merge sort is better in the worst case but slower on this random data.

Re:Is this the simplest (and most surprising) sorting algori... by smusamashah on Tuesday October 05, 2021 @02:14PM (#28763318)
What you are seeing isn't speed but the iterations. If you see the source, I am drawing at certain location in the loop. Sometimes when swap happens, sometimes afterwards. More than speed you are seeing the steps.
Re:Is this the simplest (and most surprising) sorting algori... by chubot on Tuesday October 05, 2021 @02:51PM (#28763874)
I think that is what I mean -- when there are fewer steps in the sort, then the visualization completes faster.

So if you visualize two sorts side by side, it's obvious which ones completes faster, and that corresponds to the algorithm's speed, right?

Re:Is this the simplest (and most surprising) sorting algori... by smusamashah on Tuesday October 05, 2021 @04:57PM (#28765523)
Each draw step is one draw call. For example in some algos where there isn't a clear swap operation I draw the whole array in one step, which may or may not reflect all operations that happened before that draw call.

https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...

You can change the detail level slider while its running and see how it changes the animation. At level 1 (higher level) this and insertion are same.

Re:Is this the simplest (and most surprising) sorting algori... by recursive on Tuesday October 05, 2021 @10:00AM (#28759603)
This looks interesting, but I can't get it to do anything. I see a purple gradient square, I see some widgets on the upper right. I see a box of code on the left. None of it seems to visualize a sort or even respond to input. What do I do?
Re:Is this the simplest (and most surprising) sorting algori... by SamBam on Tuesday October 05, 2021 @10:09AM (#28759714)
It's a little confusing, but playing around with it I was able to understand it.

First of all, there's a Start button at the bottom of the right menu. Hit that and you will see that big color gradient sort itself.

However, that massive square is useless for seeing what's going on. So instead change the size to its lowest (8) and the delay to something like 400.

Now what you've got is 8 randomly-sorted columns. When you hit Start that algorithm will start sorting them each in parallel. You can just look at a single column and see the colors getting swapped. The darkest color moves to the top very quickly. This is a feature of how this particular algorithm works.

What's the point of the big square? Well, for one thing it's an interesting way to compare algorithms. Go back to the settings for a large number, a very low delay, and check off two other sorting algorithms, say Comb Sort and Heap sort. Hit Start and you'll see three very different approaches to sorting the columns.

Re:Is this the simplest (and most surprising) sorting algori... by smusamashah on Tuesday October 05, 2021 @10:02AM (#28759621)
Click Start at the bottom of control panel on right.
Re:Is this the simplest (and most surprising) sorting algori... by ColinWright on Tuesday October 05, 2021 @02:33PM (#28763594)
Is the "Parallel Merge Sort" working? It doesn't seem to be doing anything ...
Re:Is this the simplest (and most surprising) sorting algori... by smusamashah on Wednesday October 06, 2021 @10:39AM (#28773707)
Fixed
Re:Is this the simplest (and most surprising) sorting algori... by ColinWright on Wednesday October 06, 2021 @10:52AM (#28773864)
Super! Thank you.