Simple recursive sort algorithm which hard to understand

Question

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100000;
void sort(int* a, int lo, int hi)
{
    int i = lo;
    if (lo >= hi)
        return;
    for (int j = hi, mode = 1; i < j; mode > 0 ? j-- : i++)
        if (a[i] > a[j])
        {           
            swap(a[i], a[j]);
            mode = -mode;            
        }
    sort(a, lo, i - 1); 
    sort(a, i + 1, hi);
}
bool check(int* a)
{
    for (int i = 1; i < N; i++)
        if (a[i] < a[i - 1])
            return false;
    return true;
}
int main()
{
    int a[N];
    for (int i = 0; i < N; i++)
        a[i] = (i * 17 + 107) % 10;
    sort(a, 0, N - 1);
    cout << (check(a) ? "correct" : "incorrect") << endl;
    return 0;
}

I found this sort algorithm but after long time of trying to understand it I couldn't. It looks very simple and short. I think that it can be proved through invariant that any element of a[lo:i] is less than any element of a[j:hi] but I can't prove that statement holds true after every iteration of loop (after j-- or i++).

Abhishek Bansal · Accepted Answer · 2013-12-12 16:46:21Z

7

It is a modified version of quicksort with 1st element as the pivot.

The algorithm basically does the following:

It has two pointers, i starting at 0, and j starting at length-1.

It keeps decrementing j untill a[j] < a[i]. At this point it swaps their values.
After this, j stays at that value, and i starts incrementing again untill a[j] < a[i]. At this point it again swaps their values and now again j starts decrementing.

Hence if you see, every comparison is being done with the 1st element. After the loop ends, the 1st element lands up in its correct place.

edited Dec 12, 2013 at 16:46

answered Dec 12, 2013 at 16:41

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

eXXXXXXXXXXX2 Over a year ago

Tricky partition procedure from quick sort) Thanks for explanation

Abhishek Bansal Over a year ago

Yes its implementation is very confusing.

Collectives™ on Stack Overflow

Simple recursive sort algorithm which hard to understand

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related