News for hackers. Stuff that matters.
Re:Is this the simplest (and most surprising) sorting algori... by maltalex on Tuesday October 05, 2021 @09:21AM (#28759037)
tl;dr the algorithm (the array is 1-based):

  for i = 1 to n do
    for j = 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 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.
Re:Is this the simplest (and most surprising) sorting algori... by klyrs on Tuesday October 05, 2021 @01:14PM (#28762350)
Viewing this as an "algorithm" may be why people find it to be surprising*. I don't find it terribly surprising, because I've played with a lot of sorting networks. Viewed as a sorting network, it's really clear how and why the algorithm works (and where it wastes half of its time).

* though, edflsafoiewq's analysis is nice and tidy

edit: https://imgur.com/a/gXYE2Ru

Re:Is this the simplest (and most surprising) sorting algori... by SketchySeaBeast on Tuesday October 05, 2021 @09:39AM (#28759304)
At first it's entirely un-intuitive and obviously slow, but I kind of like the elegance, and the use of "<" makes sense once you realize that the final sweep will be with an i at the end of the array so that j will be ahead of it.
Re:Is this the simplest (and most surprising) sorting algori... by sunnyque on Tuesday October 05, 2021 @10:35AM (#28760052)
for almost two decades I thought this is a bubble sorting algorithm
Re:Is this the simplest (and most surprising) sorting algori... by Jtsummers on Tuesday October 05, 2021 @10:55AM (#28760347)
Bubble sort only swaps adjacent pairs (thus "bubble", visualized the values "bubble up" to their correct spot) and is often abbreviated so that the inner loop runs on shorter segments (because the smallest or largest value, depending on how you write it, has been placed, no need to check that section again). this algorithm will swap non-adjacent pairs, making it more like insertion sort.
Re:Is this the simplest (and most surprising) sorting algori... by hwers on Tuesday October 05, 2021 @09:23AM (#28759059)
what does 1-based mean?
Re:Is this the simplest (and most surprising) sorting algori... by calebegg on Tuesday October 05, 2021 @09:24AM (#28759068)
The first element of the array is A[1], rather than A[0] like it would be in nearly all programming languages.
Re:Is this the simplest (and most surprising) sorting algori... by goatlover on Tuesday October 05, 2021 @11:38AM (#28760907)
Nearly all meaning the non-scientific computing ones, and particularly the ones with syntax inspired by C. Fortran, APL, Matlab, Wolfram, Mathematica, R, Julia, Cobol, Smalltalk and Lua are all 1-based, at least by default.
Re:Is this the simplest (and most surprising) sorting algori... by Scarblac on Tuesday October 05, 2021 @01:36PM (#28762713)
Or maybe not so much inspired by C, but inspired by similar arguments as Dijkstra makes in his "Why numbering should start at zero": https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/E....
Re:Is this the simplest (and most surprising) sorting algori... by dredmorbius on Tuesday October 05, 2021 @09:29AM (#28759154)
There is of course the compromise position of 0.5.
Re:Is this the simplest (and most surprising) sorting algori... by DougBTX on Tuesday October 05, 2021 @09:44AM (#28759373)
Re:Is this the simplest (and most surprising) sorting algori... by Joker_vD on Tuesday October 05, 2021 @11:07AM (#28760486)
Huh. I thought it was obvious: e.g., the top-left corner of the screen is (0, 0), the bottom-right corner is (640, 480), and pixels are 1x1 — we take the coordinate of their top-left corner to be their coordinate, so the top-left pixel has coordinates (0, 0), and the bottom-right one has (639, 479), and obviously the coordinates of their centres are (0.5, 0.5) and (639.5, 479.5).

But apparently some people treated pixels as geometrical points without size?

Re:Is this the simplest (and most surprising) sorting algori... by foxfluff on Tuesday October 05, 2021 @01:19PM (#28762431)
It's normal in signal processing to treat samples (whether audio or image) as points. A lot of things stop making sense if you replace them with line segments and rectangles.
Re:Is this the simplest (and most surprising) sorting algori... by tom_ on Tuesday October 05, 2021 @09:41AM (#28759342)
I prefer 9. It makes no less sense than 1, but it is conveniently much closer to the + and - keys.
Re:Is this the simplest (and most surprising) sorting algori... by notriddle on Tuesday October 05, 2021 @09:55AM (#28759531)
My 0 key is twice as big as the rest of the digits.
Re:Is this the simplest (and most surprising) sorting algori... by Scarblac on Tuesday October 05, 2021 @01:31PM (#28762633)
Why compromise? Just have a helpful variable like Perl's $[ to set the first element index.
Re:Is this the simplest (and most surprising) sorting algori... by goohle on Tuesday October 05, 2021 @09:51AM (#28759480)
Which is rounded down to 0 or up to 1 at random.
Re:Is this the simplest (and most surprising) sorting algori... by fullstop on Tuesday October 05, 2021 @09:25AM (#28759087)
The array indexes start at 1, not 0.
Re:Is this the simplest (and most surprising) sorting algori... by red_trumpet on Tuesday October 05, 2021 @09:24AM (#28759073)
It's entries are A[1], A[2],...,A[n] instead of A[0], A[1],...,A[n-1].
Re:Is this the simplest (and most surprising) sorting algori... by jimmyed on Tuesday October 05, 2021 @09:24AM (#28759076)
It means you probably shouldn't be on Hackernews
Re:Is this the simplest (and most surprising) sorting algori... by castis on Tuesday October 05, 2021 @09:32AM (#28759208)
It means they should definitely be on HN where they're very likely to learn new things.
Re:Is this the simplest (and most surprising) sorting algori... by ZeroCool2u on Tuesday October 05, 2021 @09:37AM (#28759277)
Welcoming open, thoughtful discussion and having people much smarter and with more experience than myself available to answer questions in which I'm not an expert is one of the main reasons I frequent HN.
Re:Is this the simplest (and most surprising) sorting algori... by findalex on Tuesday October 05, 2021 @09:41AM (#28759331)
> too young to know FORTRAN.

If you don't know, you don't know.

Re:Is this the simplest (and most surprising) sorting algori... by demosito666 on Tuesday October 05, 2021 @09:24AM (#28759071)
aka bubble sort
Re:Is this the simplest (and most surprising) sorting algori... by miloignis on Tuesday October 05, 2021 @09:26AM (#28759113)
It is definitely not bubble sort, which only uses a single index comparing items next to each other in the array.
Re:Is this the simplest (and most surprising) sorting algori... by balefrost on Tuesday October 05, 2021 @09:29AM (#28759158)
Check the direction of the comparison, and check the bounds of the loops. It's not really bubble sort.
Re:Is this the simplest (and most surprising) sorting algori... by recursive on Tuesday October 05, 2021 @09:57AM (#28759551)
And check whether the compared elements are adjacent.