#include <iostream>
#include <iomanip>

using namespace std;

template<typename T>
void quickSort1(T* array, long N)
{
    long i = 0, j = N - 1;
    T p = array[N >> 1];

    do {
        while (array[i] > p) i++;
        while (array[j] < p) j--;

        if (i <= j) {
            T temp = array[i]; array[i] = array[j]; array[j] = temp;
            i++; j--;
        }
    } while (i <= j);

    if (j > 0) quickSort1(array, j+1);
    if (N > i) quickSort1(array + i, N - i);
}

int main(int argc, char * argv[])
{
    int a[40];
    for(int i = 0; i < 40; ++i) a[i] = rand()%100;
    for(int i: a) cout << i << " "; cout << "\n";
    quickSort1(a,40);
    for(int i: a) cout << i << " "; cout << "\n";
}