#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, given a partition of any permutation of an
array with respect to a certain pivot, that partition
will also be a partition of the initial array with respect
to the same pivot. It means that finding a partition of
a permutation of the initial array is enough.
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 will be 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, all elements in the initial array with indexes between
0 and current will satisfy the condition: no element being greater
than or equal to the pivot is situated before an element being
less than the pivot. This is, of course, equivalent with the following:
all elements with indexes <= current being less than the pivot are at the
beginning of the array, in an arbitrary order, followed by those greater
than or equal to the pivot (This only applies to the elements with indexes
between 0 and current! We cannot say anything about the rest of the array
yet). Also, end represents the index of the first element greater than
or equal to the pivot in the array.

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], 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 ordering condition
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 no element of index <=n that is greater than the pivot or equal
to the pivot stays before an element less than the pivot.
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.

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.
It is important to mention that this partitioning scheme splits the
array in 2 parts: the part < pivot and the part >= pivot. If multiple
array elements are equal to the pivot, it is not guaranteed that they will
be at consecutive indexes in the array. For that to happen, we should
use a partitioning scheme that splits the array in 3 parts: < pivot,
= pivot, > pivot. One example of such a partitioning scheme is Hoare's.

*/
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;
}