//
//  main.cpp
//  quick_sort
//
//  Created by Alex Danilov on 22/01/2018.
//  Copyright © 2018 Alex Danilov. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr = {3, 6, 2, 1, 0, -8, 10, 33};

void swap(int* a, int* b) {
    int c = *a;
    *a = *b;
    *b = c;
}

int sep(int f, int l) {
    int pivot = arr[l];

    int i = f - 1;
    for (int j = f; j < l; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[l]);
    return i + 1;
}


void quick_sort(vector<int> arr, int f, int l) {
    if (f < l) {
        int i = sep(f, l);

        quick_sort(arr, f, i - 1);
        quick_sort(arr, i + 1, l);
    }
}

int main() {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quick_sort(arr, 0, arr.size()-1);

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }

    return 0;
}