Why does this sort algorithm work?

Problem Detail: 

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 

Asked By : darkblue

Answered By : Ran G.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45348