3
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Aug 17 '15 at 14:20
9
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The key thing to notice is that you just explained Insertion sort. $\endgroup$ – PleaseHelp Aug 18 '15 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.