CODEWITHSUNDEEP
c++algorithmsorting
eXXXXXXXXXXX2
eXXXXXXXXXXX2

Reputation: 1580

Simple recursive sort algorithm which hard to understand

#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++).

Upvotes: 3

Views: 173

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

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.

Upvotes: 7

Related Questions