#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];
  cout << "pivot = " << pivot << ", at position " << pivpos << "\n";
  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; }

int main()
{ srandomdev();
  int A[12];
  for (int i = 0; i < 12; i += 1)
    A[i] = random() % 100;
  for (int i = 0; i < 12; i += 1)
    cout << A[i] << " ";
  cout << "\n";
  int p = partition(A, 0, 11);
  for (int i = 0; i < 12; i += 1)
    cout << A[i] << " ";
  cout << "\n"; }