#include <iostream>

using namespace std;

int random_in_range(int a, int b)
{ return random() % (b - a + 1) + a; }

int partition(int A[], int start, int end)
{ int orig_end = end;
  int pivpos = random_in_range(start, end);
  int pivot = A[pivpos];
  swap(A[pivpos], A[end]);
  end -= 1;
  while (true)
  { while (A[start] < pivot)
      start += 1;
    while (A[end] >= pivot)
      end -= 1;
    if (start > end)
      break;
    swap(A[start], A[end]);
    start += 1;
    end -= 1; }
  swap(A[start], A[orig_end]);
  return start; }

void quicksort(int A[], int start, int end)
{ if (start >= end)
    return;
  int p = partition(A, start, end);
  quicksort(A, start, p-1);
  quicksort(A, p+1, end); }

int main()
{ srandomdev();
  const int N = 25;
  int A[N];
  for (int i = 0; i < N; i += 1)
    A[i] = random() % 100;
  for (int i = 0; i < N; i += 1)
    cout << A[i] << " ";
  cout << "\n";

  quicksort(A, 0, N-1);

  for (int i = 0; i < N; i += 1)
    cout << A[i] << " ";
  cout << "\n"; }