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

void swap(int *x, int *y) {
  int aux = *x;
  *x = *y;
  *y = aux;
}

/*
Proof of the partitioning scheme:

Instead of directly partitioning the nums array,
we will partition a permutation of the nums array.

Indeed, a partition is independent of the order of the elements in
an array. If we find a correct partition of a permutation of the array,
that partition will also be correct for the initial array.

Say our pivot is nums[pivotIndex]. Let's swap nums[pivotIndex]
and nums[numsSize-1], so that our pivot is at the end of the
array. We will partition this permutation with respect to
its last element (its last element is the pivot).

The goal of this partitioning scheme is to split the array in 2 parts:
1. The part with elements < the pivot.
2. The part with elements >= the pivot.

Note that a partition that also includes a part with elements = pivot
is also possible (Hoare's partitioning), but it's a different algorithm.
The partition I use here only puts one element which is =  to the pivot in
its correct place (if there are multiple elements equal to the pivot,
not all of them are in their correct place).

Call a partition of an array with respect to a pivot a permutation of
the initial array with the property: no element greater than or equal
to the pivot is before an element lower than the pivot.

We will prove that the partitioning scheme is correct, using
induction:

P(n): At current = n, 0<=n<=numsSize-2, after checking the if
condition, the structure of the array is as follows:

1. The resulting subarray with indexes 0,...,current is a partition of the
initial subarray with indexes 0,...,current (with respect to the chosen
pivot).

2. The resulting subarray with indexes current+1,..., numsSize-2 is not
modified.

3. end is the index of the first element in the resulting array that is
greater than or equal to the pivot.

P(0): We compare nums[0] with the pivot. Regardless of the result,
the array remains the same, as swapping nums[0] with nums[end], where end = 0,
has no effect. However, if nums[0] is less than the pivot, end is incremented
by 1. Hence, the induction claim holds trivially for the structure conditions
and end is updated correctly.
P(n) -> P(n+1):
At current = n+1 we check if nums[n+1] is less than the pivot.
We know that the elements with indexes <=n form a partition of the
initial subarray.
We also know that end is the index of the first element greater than
the pivot. So, if nums[n+1] is less than the pivot, we swap
it with the first >= element. So the ordering condition remains true.
Also, end continues to be correctly chosen.
If nums[n+1] is >= pivot, no action is taken and the ordering condition
holds, as well as the correctness of end. So P(n+1) is true, as the
rest of the array remains unmodified.

From induction, P(n) is true, 0<=n<=numsSize-2, so P(numsSize-2) is true.
Swap the last element (the pivot) with nums[end] and we will obtain
a partition, with the pivot at its right index.
In fact, we partition the array except for its last element (the pivot),
which will be swapped at the end.

*/
int partition(int *nums, int numsSize, int pivotIndex) {
  int current, end = 0;
  swap(&nums[pivotIndex], &nums[numsSize - 1]);
  for (current = 0; current < numsSize - 1; current++) {
    if (nums[current] < nums[numsSize - 1]) {
      swap(&nums[current], &nums[end]);
      end++;
    }
  }
  swap(&nums[end], &nums[numsSize - 1]);
  return end;
}

// Here, numsSize is the size = number of elements of the nums array.
void quicksort(int *nums, int numsSize) {
  if (numsSize <= 1) return;
  int pivotIndex = rand() % numsSize;
  int pivot = nums[pivotIndex];
  int pos = partition(nums, numsSize, pivotIndex);
  // Recursive calls on smaller arrays.
  quicksort(nums, pos);
  // pos+1, ... numsSize-1 (numsSize-1-pos)
  quicksort(nums + pos + 1, numsSize - 1 - pos);
}

int main() {
  int *v, n, i;
  FILE *fp_in, *fp_out;
  fp_in = fopen("algsort.in", "r");
  fp_out = fopen("algsort.out", "w");
  srand(time(NULL));
  fscanf(fp_in, "%d\n", &n);
  v = (int *)malloc(n * sizeof(int));
  for (i = 0; i < n; i++) fscanf(fp_in, "%d ", &v[i]);
  quicksort(v, n);
  for (i = 0; i < n; i++) fprintf(fp_out, "%d ", v[i]);
  fclose(fp_in);
  fclose(fp_out);
  return 0;
}