#include <bits/stdc++.h>

using namespace std;

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

int part_sort(int arr[], int l, int r)
{
    int pivot = arr[l];
    int i = r + 1;
    for (int j = r; 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(int arr[], int l, int r)
{
    int st_arr[r - l + 1];
    int top = -1;
    st_arr[++top] = l;
    st_arr[++top] = r;
    while (top >= 0)
    {
        r = st_arr[top--];
        l = st_arr[top--];
        int p = part_sort(arr, l, r);
        if (l < p - 1)
        {
            st_arr[++top] = l;
            st_arr[++top] = p - 1;
        }
        if (p + 1 < r)
        {
            st_arr[++top] = p + 1;
            st_arr[++top] = r;
        }
    }
}

int main()
{
    setlocale(LC_ALL, "Russian");
    cout << "Введите длину массива: ";
    int n;
    cin >> n;
    int *arr = new int[n];

    cout << "Введите 1, если хотите вручную ввести значения," << endl;
    cout << "или любое другое число, если хотите срандомить: " << endl;

    int check;
    cin >> check;

    cout << endl;
    cout << "Исходный массив: " << endl;

    if (check == 1)
        for (int i = 0; i < n; i++)
            cin >> arr[i];
    else
    {
        for (int i = 0; i < n; i++)
        {
            arr[i] = rand() % n + 1;
            cout << arr[i] << " ";
        }
        cout << endl;
    }
    quick_sort(arr, 0, n - 1);
    cout << endl;
    cout << "Массив после сортировки: " << endl;
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}