#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <fstream>
using namespace std;

void Partition(int* masyv, int a) {

    if (a <= 1) {
        return;
    }

    int Pivot = masyv[rand() % a];
    int low = 0;
    int high = a - 1;

    while (low < high) {
        while (masyv[low] < Pivot) {
            ++low;
        }
        while (masyv[high] > Pivot) {
            --high;
        }

        int iTemp       = masyv[low];
        masyv[low]     = masyv[high];
        masyv[high]     = iTemp;
    }

    Partition(masyv, low);
    Partition(&(masyv[low + 1]), a - low - 1);
}

void Quicksort(int* masyv, int a) {
    srand((unsigned int)time(0));
    Partition(masyv, a);
}

int main() {

    int a;
    ifstream failas;
    failas.open("info.txt");
    failas>>a;
    int masyv[a];
    cout<<"Nuskaityti skaiciai: \n";
        for (int i=0;i<a;i++)
        {
            failas >>masyv[i];
            cout<<masyv[i]<<" ";
        }
    cout<<"\nnuskaitymas baigtas...\n-------------------------------------\n";
    Quicksort(masyv, a);

    cout<<"Surikiuoti skaiciai: \n";
        for (int i = 0; i < a; i++){
            cout << masyv[i] << " ";
        }

    return 0;
}