Why does this sort algorithm work?

Question

The following O(n^2) sorting algorithm works but I can't figure out why.

array a // length n, indexed 0 to n-1 

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

It seems it is not bubble sort as after a single iteration neither the minimum or maximum is in place. (And also it needs n^2 comparisons instead of n*(n-1)/2)

How would you prove this algorithm sorts ? How is this sort algorithm called?

An execution of the sort for the example :

initial target
194600925
592040703
20865352
814014281
792862803

target after iteration 0
814014281
194600925
20865352
592040703
792862803

target after iteration 1
194600925
814014281
20865352
592040703
792862803

target after iteration 2
20865352
194600925
814014281
592040703
792862803

target after iteration 3
20865352
194600925
592040703
814014281
792862803

target after iteration 4
20865352
194600925
592040703
792862803
814014281

Answer 1

It is a variant of bubble sort, however the endpoints of the array shift throughout the progress of the algorithm.

In particular it maintains the following invariant:

at the end of the $i$-th iteration, the elements in indices $1..i$ are sorted.

At the first step it finds the maximal element and puts it in index 1. (prefix length =1). Then, at every iteration $i$ it adds the element in position $i$ to the prefix, and performs a (degenerate) bubble sort on the first $i$ indices. This bubble sort takes only one step since except for the one new element, the other $i-1$ elements are already sorted. The maximal element will now be at position $i$. The length of the sorted prefix keeps increasing at every iteration until the entire array is sorted.

I don't know if this sorting approach has a name. It looks like a type of insertion sort.

Answer 2

Let the array $a$ be indexed from $0$ to $n-1$ with elements $a[0]a[1]...a[n-1]$.

What the for loop does : Starting from index $0$ to $n-1$, for every such index $i$ it traverses the whole array from index $0$ to $n-1$ and during traversal it swaps the current element at index $t$ being traversed with $a[i]$ if $a[i]\le a[t]$ and continues the traversal (with $a[i]$ changed).

What is happening :

Iteration for index $0$ : The maximum element comes at index $0$ .

Now the algorithm behaves as insertion sort for iteration $1$ to $n-1$ but with redundant comparisons during the array traversal for each iteration.

Every comparison after index $i-1$ made during "iteration for index $i$" is redundant since the maximum element should already be at index $i-1$ due to previous iteration resulting in no further swapping in current iteration.

Answer 3

The redundant comparisons cloud the picture. It becomes much more clear what is happening if you focus on just the right portion.

We can ignore any case where i=j, comparing a position to itself doesn't matter.

The first pass with i=0 puts the largest value in a[0]. After that each pass will keep moving the largest value into a[i]. Any further comparison where j>i will always fail, because a[i] will already be the largest. We can ignore any case where j>i.

The key is to focus on what's happening when j<i.

For each pass of i, consider the sublist from a[0] to a[i].

The first pass, i=0, our sublist is just a[0]. The first pass puts the largest element in a[0]. A list with just one element is inherently "sorted".

The second pass, i=1, our sublist is a[0] to a[1]. a[0] is the largest value, a[1] holds some new value to consider. The new value is always smaller, and always gets swapped to the bottom at a[0]. Our sublist a[0] to a[1] is sorted.

The third pass, i=2, our sublist is a[0] to a[2]. a[0] to a[1] is sorted, a[2] holds some new value to consider. The smallest value of our sublist is either a[0], or the new value at a[2]. The smallest value goes into a[0]. Then the next smallest value goes into a[1]. This pushes the largest value up into a[2]. Our sublist a[0 to 2] is sorted.

When i=3, the same thing happens. A new value enters the picture a[3]. Any values smaller than a[3] are left unaffected at the bottom, then a[3] gets inserted, and anything larger than a[3] gets bumped up one position. The sublist a[0 to 3] is now sorted, with the absolutely largest value in a[3].

Each pass of i brings in one new value, inserting it to make a sorted sublist from a[0] to a[i]. The last pass of i brings in the final value, and our sorted sublist fills the entire list.