#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

inline void Swap(int *A, int *B)
{
    int aux = *A;
    *A = *B;
    *B = aux;
}

void PrintArray(FILE *file_out, int *Arr, int Size)
{
    int i;
    for (i = 0; i < Size; ++i)
        fprintf(file_out, "%d ", *(Arr + i));
}

int Partition(int *arr, int low, int high)
{
    int pivot = arr[high];
    //alegem pivotul random
    int smallerIndex = low - 1;
    int index;
    for (index = low; index < high; ++index)
    {
        if (arr[index] < pivot)
        {
            Swap(&arr[index], &arr[++smallerIndex]);
        }
    }
    Swap(&arr[++smallerIndex], &arr[high]);
    //punem pivotul pe pozitia corespunzatoare
    return smallerIndex;
}

void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        srand(time(NULL));
        int randomPosition = low + rand() % (high - low);
        Swap(&arr[high], &arr[randomPosition]);

        int pivot = Partition(arr, low, high);

        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

int main()
{
    int i;
    int *arr, size;

    FILE *file_in, *file_out;
    file_in = fopen("algsort.in", "r");
    file_out = fopen("algsort.out", "w");

    fscanf(file_in, "%d", &size);
    arr = (int*)malloc(sizeof(int) * size);
    for (i = 0; i < size; ++i)
        fscanf(file_in, "%d", arr + i);

    QuickSort(arr, 0, size - 1);
    PrintArray(file_out, arr, size);

    
}