//
//  main.m
//  alg
//
//  Created by Sergey Demchenko on 10/6/16.
//  Copyright © 2016 Antrix. All rights reserved.
//

#import <Foundation/Foundation.h>

int randomNumberBetween(int min, int max)
{
    return min + arc4random_uniform(max - min + 1);
}

void swap(NSMutableArray *array, int i, int j)
{
    id tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

BOOL less(id a, id b)
{
    return [a compare:b] == NSOrderedAscending;
}

void shuffle(NSMutableArray *array)
{
    for (int i = 0; i < array.count; i++) {
        int r = randomNumberBetween(0, i);
        swap(array, i, r);
    }
}

int partitioning(NSMutableArray *array, int lo, int hi)
{
    int i = lo;
    int j = hi + 1;

    while (true) {
        while (less(array[++i], array[lo])) {
            if (i == hi) { break; }
        }

        while (less(array[lo], array[--j])) {
            if (j == lo) { break; }
        }

        if (i >= j) { break; }
        swap(array, i, j);
    }

    swap(array, lo, j);

    return j;
}

void sortInternal(NSMutableArray *array, int lo, int hi)
{
    if (hi <= lo) { return; }
    int j = partitioning(array, lo, hi);
    sortInternal(array, lo, j - 1);
    sortInternal(array, j + 1, hi);
}

void sort(NSMutableArray *array)
{
    shuffle(array);
    sortInternal(array, 0, (int)array.count - 1);
}

void invoke()
{
    NSMutableArray *array = [@[ @11, @3, @7, @2, @5, @14, @1, @25] mutableCopy];
    sort(array);

    NSLog(@"%@", array);
}

int main(int argc, const char * argv[])
{
    @autoreleasepool {
        invoke();
    }
    return 0;
}