Interesting new sort algorithm...

[westfw]

There's an interesting new sort algorithm:

Algorithm (1) ICan’tBelieveItCanSort(A[1..n])

Code: [Select]

//sorts an array A of n elements in non-decreasing order.
for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]


https://arxiv.org/pdf/2110.01111.pdf


FTA:

There is nothing good about this algorithm. It is slow – the algorithm
obviously runs in Θ(n2) time, whether worst-case, average-case or best-case.
It unnecessarily compares all pairs of positions, twice (but see Section 3).
There seems to be no intuition behind it, and its correctness is not entirely
obvious. You certainly do not want to use it as a first example to introduce
students to sorting algorithms. It is not stable, does not work well for
external sorting, cannot sort inputs arriving online, and does not benefit
from partially sorted inputs. Its only appeal may be its simplicity, in terms
of lines of code and the “symmetry” of the two loops.

[ataradov]

How is this new? Is not this a thing that you would naturally implement if you are just starting programming and don't know anything about sorting?

This is just compare every element with every other element. This can be quickly optimized to bubble sort pretty much by anyone interested in spending some time. The rest of the sorting algorithms are much less obvious. 

[magic]

Hardly new.

Code: [Select]

for i = 1 to n do
  for j = 1 to i do
    if A[i] < A[j] then
      swap A[i] and A[j]
This is a simple implementation of Insertion Sort. Find one difference.
Their version simply performs some additional pointless work. Their big discovery is that the extra work is actually harmless.

[SiliconWizard]

Fascinating use of public money.

[gamalot]

Isn't this the famous bubble sort method?

[magic]

Fascinating use of public money.

I have read a scientific paper which basically demonstrated that splitting a certain obviously parallelizable task onto two processors brings the expected 200% speedup. Apparently multiprocessing is a big theme in this decade

Now, that has me wondering what's the fastest time a for-all-practical-purposes-infinitely-core machine could sort an array of N elements, hmm...

[golden_labels]

arXiv is a publication service with no peer review. It is moderated, but with the focus on content relevance and meeting some minimal quality. The person given as the author does not list this work among his publications.⁽¹⁾ Which makes me think that may be a joke, an attempt to discredit the author or arXiv. —2022-07-25 update: the publication is authentic.

However, if that’s neither of the above, that’s not as absurd as it may seem. It’s not describing bubble sort. The paper explores an algorithm, that at a first glance should not work, and explains its operation.

⁽¹⁾ Stanley Fung’s DBLP entry contains this position, but that is merely an automatic indexer.

[KaneTW]

Why shouldn't it work on first glance? The invariants are really obvious.

[xrunner]

Well if you've never seen it before it's new ... to you. 

[ledtester]

How is this new? Is not this a thing that you would naturally implement if you are just starting programming and don't know anything about sorting?

This is a simple implementation of Insertion Sort. Find one difference.
Their version simply performs some additional pointless work. Their big discovery is that the extra work is actually harmless.

Why shouldn't it work on first glance? The invariants are really obvious.

Consider if A is already non-decreasing, i.e. A[1] < A[2] < ... < A[n].

The first thing the algorithm does is swap A[1] with A[2]. Yet in the end it fixes this mistake.

You can play with it here (tutorialspoint.com's online python environment):

http://tpcg.io/_VG4MZM

[Nominal Animal]

Ledtester hit the nail on the head.

Is not this a thing that you would naturally implement if you are just starting programming and don't know anything about sorting?

No, because the condition of when to swap is reversed to what one would expect from the description and results.

I, too, missed that on the first read.

[TheCalligrapher]

It is indeed an interesting algorithm.

At the first sight it appears that all it does is find the largest element of the entire array and put into i-th postion after each iteration of the outer cycle.

However, the non-obvious part is that it leaves a sorted array in its wake (to the left of the current i-th position).

The article is essentially dedicated to proving the latter.

[brucehoult]

Isn't this the famous bubble sort method?

No.

[brucehoult]

It is indeed an interesting algorithm.

At the first sight it appears that all it does is find the largest element of the entire array and put into i-th postion after each iteration of the outer cycle.

However, the non-obvious part is that it leaves a sorted array in its wake (to the left of the current i-th position).

The article is essentially dedicated to proving the latter.

I saw it the other way around.

In each inner loop, while j < i it inserts element i in the correct place in the already-sorted part of the array. This is standard insertion sort.  While j > i it puts the largest remaining at position i -- essentially a selection sort in reverse order.

After each outer loop the invariant is:

< i: sorted
= i: largest unsorted element
> i: almost original order, but largest elements permuted, stays untouched if original data is in descending order.

[brucehoult]

You can play with it here (tutorialspoint.com's online python environment):

http://tpcg.io/_VG4MZM

It's more illuminating if you print the array after each outer loop:

Code: [Select]

import random

def ICantBelieveItCanSort(a):
    n = len(a)
    for i in range(n):
        print(a)
        for j in range(n):
            if a[i] < a[j]:
                a[i], a[j] = a[j], a[i]

a = list(range(100,120))
random.shuffle(a)
ICantBelieveItCanSort(a)
print(a)


[Mechatrommer]

Isn't this the famous bubble sort method?

no, it is a joke... but if you have no other option, at least you can change...

Code: [Select]

for i = 1 to n do
  for j = 1 to n do
to

Code: [Select]

for i = 1 to n do
  for j = i to n do


[brucehoult]

Isn't this the famous bubble sort method?

no, it is a joke... but if you have no other option, at least you can change...

Code: [Select]

for i = 1 to n do
  for j = 1 to n do
to

Code: [Select]

for i = 1 to n do
  for j = i to n do


That will sort in the opposite order.

"for j = 1 to i" will sort in the same order.

[AndyBeez]

In olden days when Cobol and Fortran were coding monarchy, learning the pros and cons of each sort algorithm was computer science 101. Today, few programmers understand why or even how a sort works, because that's in the voodoo the compiler does.

But... if you're interested, and have a few hours study time, the sorting algorithms are described here:

https://www.geeksforgeeks.org/sorting-algorithms/

My favourite is the "Gnome Sort"

[Mechatrommer]

Isn't this the famous bubble sort method?

no, it is a joke... but if you have no other option, at least you can change...

Code: [Select]

for i = 1 to n do
  for j = 1 to n do
to

Code: [Select]

for i = 1 to n do
  for j = i to n do


That will sort in the opposite order.

"for j = 1 to i" will sort in the same order.

from quick look, op is an inefficient sort in decreasing order, so by the end of first run i=1, the biggest number is already in A (1), so no need to check index 1 in 2nd run. Same thing happened when sort in increasing order by switching the comparison sign check. But no, the op is indeed a joke because it will move back the biggest number to the end, after it went to the first during 1st run.. a waste of pure O(n^2)  complexity instead of a somewhat better O(n(n+1)/2).

[gamalot]

Isn't this the famous bubble sort method?

no, it is a joke... but if you have no other option, at least you can change...

Code: [Select]

for i = 1 to n do
  for j = 1 to n do
to

Code: [Select]

for i = 1 to n do
  for j = i to n do


My bad, I should have looked more closely. 

[magic]

It’s not describing bubble sort. The paper explores an algorithm, that at a first glance should not work, and explains its operation.

However, the non-obvious part is that it leaves a sorted array in its wake (to the left of the current i-th position).

First of all, to all the Bubble Sort fanboys, yours is not the only trivial O(n²) sorting algorithm known to man. Learn the others, and you may even recognize them when you see them.

The idiocy "invented" by that guy is an inefficient implementation of Insertion Sort, and Insertion Sort is actually the best sorting algorithm in the world (except when doing large arrays with efficiency) and it should be the go-to choice for everyone's trivial sorting needs and taught at every beginner programming course instead of the BS nonsense.

This is your usual (ascending) insertion sort. You take each element, and shift it towards the beginning until it fits. Everything to the left of i is now sorted and when i reaches the end, you're done. Two for loops, four lines of code. Fast on already-sorted arrays and cache-friendly.

Code: [Select]

for i = 2 to n do
  for j = i down to 2 do
    if A[j] < A[j-1] then
      swap A[j] and A[j-1]A speed-optimized implementation will add

Code: [Select]

    else
      break out of the inner loop and take next ibecause all further comparisons are pointless.

A slightly less efficient implementation below. Here, we scan from the left, find the right place for A(i) and then shift all displaced elements to the right, using the now-emptied i array slot as temporary storage. Note that after the first swap, the if condition will always be true and there is no opportunity for eliminating some iterations of the inner loop.

Code: [Select]

for i = 2 to n do
  for j = 1 to i-1 do
    if A[i] < A[j] then
      swap A[i] and A[j]
And here's what the guy "invented".

Code: [Select]

for i = 1 to 1 do
  // do useless work before the sorting even began
for i = 2 to n do
  for j = 1 to i-1 do
    if A[i] < A[j] then
      swap A[i] and A[j]
  for j = i to n do
    // do useless work on not-yet-sorted part of the array
And finally, 100% equivalent to the above, but obfuscated implementation, which is clearly above the head of your average computer scientist and software developer

Code: [Select]

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

[Picuino]

I have post in another thread a program to compare different sorting algorithms:
https://www.eevblog.com/forum/programming/comparison-of-sorting-algorithms/msg4317196/#msg4317196

I'm going to add this 'new' algorithm to comparison.

[SiliconWizard]

When comparing it with bubble or insertion sort, you need to consider the order of the loop indices, which will give you a hint.
The article explains why it is not obvious at first sight, so for those wondering, just read it.

While in the end, this "algorithm" is completely useless per se, for people studying (or brushing up on) how to prove algorithm correctness, this can be a nice simple exercise, so that's where I would put the value of this article.

Being able to prove/disprove algorithm correctness is a very valuable skill.

[AndyBeez]

An issue with a sorting algo is just how random or discrete the input data is. Sorting 'assumes' the probability that a range of values are randomly distributed. Thus the chance of a range reading BDACE is the same as EDCBA and even ABCDE. The standard deviation is 0.5 (There is no 'entropy' to the randomness ).

But real world, data is 'clumpy'. Consider a sort algo for US states. We have clustering around states starting A M and N, and no states starting E J and Y. Thus, an efficient high speed algo would/could/should consider the data's underlying distribution(entropy); by weighting the existence or absence of value ranges. This is far beyond my school maths

[Nominal Animal]

An issue with a sorting algo is just how random or discrete the input data is. [...] This is far beyond my school maths

It's not nearly as difficult to quantify as one would believe; algorithm analysis isn't hard per se, it's one of those things where the hurdle is to understand the concepts first, and then the mathy part is almost always very easy.

A first approximation is to examine the best case cost, amortized average cost, and the worst-case cost, and estimate how often do each of them occur.

You can trivially instrument your sort function to count the number of comparisons and swaps (or whatever primitives it uses), and then examine how they vary for different inputs.

One interesting and practically useful way to examine the statistical distribution of the complexity of a sort operation –– that is, how it behaves for different sortednesses of input –– is to start with perfectly ordered data (one case is preferred order, and the other is inverse order), and then increasingly shuffle it (using a known good pseudorandom shuffle; this is very important), while counting the number of operations when sorting the shuffled data.  You do this a few times in parallel, and you get an excellent statistical picture of how the sort behaves overall.

(Note that if you have N elements in the array, you only need a comparable amount, say 7N, of shuffle operations (insertions or swaps) to "completely randomize it".  So this is also a very practical way of characterising a sort operation in terms of its primitives.)

In general, for a good sort function with bad worst case behaviour (like say Quicksort), you want the number of operations descend very quickly from the worst case towards the minimum, with minimum obtained for most inputs, as the amount of shuffle/"randomness" in the original data increases.

As to benchmarking actual sorting code, the key is to always use real-world data.  Current computers are so complex wrt. timing that microbenchmarks just don't cut it.

When you have large enough arrays, the cache access pattern of the data becomes a bottleneck, unless your data structures are not amenable to sorting anyway.  (When sorting say floating-point numbers, it can be done in linear time, since there is a fixed number of possible keys, using a radix sort.  Because of its cache behaviour, it just is slower than asymptotically worse sort algorithms (those with O(N log N) time complexity in particular) until N becomes unreasonably large, something on the order of 10⁹ or larger.  And even then, it usually turns out that you can do the sorting "for free" while doing other stuff to the data, due to I/O being bottleneck (so the "cost" of doing the sort then is just a bit more CPU work, but wall clock time taken is not affected.)

Then again, if you are doing sorting on the background, and you don't care how long it takes as you want to minimize the total CPU and I/O load needed to complete the sort, you need a completely different algorithm and approach compared to when there is a human waiting for the sort to complete (in which case you want to minimize the latency caused by sorting; i.e. wall clock time taken, before the human can continue doing whatever it is they are doing).

Which means that there is no "best" sorting algorithm at all, because the criteria for "goodness" depends on the use case.
To find out, all you need is time and effort.  However, today's world seems to be hell bent on just getting it done as fast as possible, so throwing a library or sort algorithm that everybody else is using on such a problem is much more commercially viable approach.  Nobody appreciates much efforts trying to compare different sort algorithms, because they've already made up their mind as to which one is superior.