#include <stdio.h>

// Funcție pentru sortarea bulelor
void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
      if (arr[j] > arr[j+1]) {
        // Schimbare elemente dacă sunt în ordine inversă
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

// Funcție pentru interschimbarea a două elemente într-un vector
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Funcție pentru a alege pivotul și a rearanja elementele în jurul pivotului
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Alegem pivotul (ultimul element)
    int i = (low - 1);  // Indexul elementului mai mic decât pivotul

    for (int j = low; j <= high - 1; j++) {
        // Dacă elementul curent este mai mic decât sau egal cu pivotul
        if (arr[j] <= pivot) {
            i++;  // Incrementăm indexul elementului mai mic
            swap(&arr[i], &arr[j]);  // Schimbăm elementele la pozițiile i și j
        }
    }
    swap(&arr[i + 1], &arr[high]);  // Aducem pivotul în poziția corectă
    return (i + 1);  // Returnăm poziția pivotului
}

// Funcție pentru a realiza QuickSort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Alegem pivotul și îl plasăm în poziția corectă
        int pi = partition(arr, low, high);

        // Sortăm recursiv cele două părți ale vectorului
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
  // Deschiderea fișierelor de intrare și ieșire
  FILE *inputFile, *outputFile;
  inputFile = fopen("algsort.in", "r");
  outputFile = fopen("algsort.out", "w");

  // Citire numărul de elemente
  int n;
  fscanf(inputFile, "%d", &n);

  // Citire elemente
  int arr[n];
  for (int i = 0; i < n; i++) {
      fscanf(inputFile, "%d", &arr[i]);
  }

  // Apelarea funcției de sortare
  quickSort(arr, 0, n-1);

  // Scrierea rezultatului în fișierul de ieșire
  for (int i = 0; i < n; i++) {
      fprintf(outputFile, "%d ", arr[i]);
  }

  // Închiderea fișierelor
  fclose(inputFile);
  fclose(outputFile);

  return 0;
}