Hacker News Reader

Comment by zoomablemind | Hacker News Reader

TFA seems to be a somewhat wasteful version of an algo which in my mind I call 'sinkersort' or 'minsort':

  for (i=0; i<n; ++i)
    for (j=i+1; j<n; ++j)
      if (a[j] < a[i])
        swap(a[j], a[i]);

Here the inner loop basically finds a min value of the remaining subset. This progressively fills the array in the sorted order.

The number of comparisons is bound by n^2/2 vs n^2 of TFA.

View on HN

Yours looks like selection sort but with more swapping.

The one in TFA isn't, for one crucial reason: the comparison is the other way around... And yet, it sorts.

> Yours looks like selection sort but with more swapping...

Well, shooting for the simplicity (as posited in the Fung's arxiv paper) -- this one is on par with TFA and somewhat simpler in expression than the selection sort.

This is also direct, less 'magical' and indeed less wasteful than TFA. So for those roll-your-own-sort moments I'd rather remember this one instead.

By the way, the TFA algo is equivalent to:

  for (i=0; i<n; ++i)
    for (j=0; j<(i ? i : n); ++j)
      if (a[i] < a[j])
        swap(a[i], a[j]);

Once the max has been swaped in, further inner iterations past i (the position of max) are redundant.

However, we can go even further:

  for (i=0; i<n; ++i)
    for (j=0; j<i; ++j)
      if (a[i] < a[j])
        swap(a[i], a[j]);

This dispenses with the explicit max swap and simply does progressive insertion.

Curiously, in such transformed form the algo echoes the 'selection sort' from my previous post, performs equivalently too (wrt ncmpr, nswp).

Reply on news.ycombinator.com