#include <stdio.h>
#include <stdlib.h>

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

int partition(int a[], int left, int right) {
    int i = left - 1;
    int pivot = a[right];
    int j;
    for(j = left; j <= right - 1; ++j) {
        if(a[j] <= pivot) {
            ++i;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i+1], &a[right]);
    return i+1;
}

void quickSort(int a[], int li, int ls) {
    if(li < ls) {
        int k = partition(a, li, ls);
        quickSort(a, li, k - 1);
        quickSort(a, k+1, ls);

    }
}

int citire(int ** v) {
    FILE * fin = fopen("algsort.in", "rt");
    if(fin == NULL) {
        printf("Eroare la deschiderea fisierului");
        exit(EXIT_FAILURE);
    }
    int n;
    fscanf(fin, "%d", &n);
    int i;
    (*v) = (int *) malloc(n * sizeof(int));
    for(i = 0; i < n; ++i) {
        fscanf(fin, "%d", &(*v)[i]);
    }
    fclose(fin);
    return n;
}

void afisare(int n, int * v) {
    FILE * fout = fopen("algsort.out", "wt");
    if(fout == NULL) {
        printf("Eroare la deschiderea fisierului");
        exit(EXIT_FAILURE);
    }
    int i;
    for(i = 0; i < n; ++i)
        fprintf(fout, "%d ", v[i]);
    //fprintf(fout, "%d", i);
    fclose(fout);
}

int main(){
    int * v = NULL;
    int n = citire(&v);
    quickSort(v, 0, n - 1);
    afisare(n, v);
    return 0;
}