Hacker News Reader

Comment by maltalex | Hacker News Reader

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]

View on HN

This is how it looks like https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...

It behaves more like insertion sort.

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?

Click Start at the bottom of control panel on right.

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.

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]

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.

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.

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.

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?

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.

Is the "Parallel Merge Sort" working? It doesn't seem to be doing anything ...

Fixed

Super! Thank you.

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

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.

for almost two decades I thought this is a bubble sorting algorithm

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.

what does 1-based mean?

The first element of the array is A[1], rather than A[0] like it would be in nearly all programming languages.

There is of course the compromise position of 0.5.

I prefer 9. It makes no less sense than 1, but it is conveniently much closer to the + and - keys.

My 0 key is twice as big as the rest of the digits.

https://www.realtimerendering.com/blog/the-center-of-the-pix...

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?

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.

Which is rounded down to 0 or up to 1 at random.

Why compromise? Just have a helpful variable like Perl's $[ to set the first element index.

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.

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....

It's entries are A[1], A[2],...,A[n] instead of A[0], A[1],...,A[n-1].

It means you probably shouldn't be on Hackernews

It means they should definitely be on HN where they're very likely to learn new things.

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.

> too young to know FORTRAN.

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

The array indexes start at 1, not 0.

aka bubble sort

It is definitely not bubble sort, which only uses a single index comparing items next to each other in the array.

Check the direction of the comparison, and check the bounds of the loops. It's not really bubble sort.

And check whether the compared elements are adjacent.

Reply on news.ycombinator.com