© 2020 Neveles. All rights reserved.

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

// вход:
// массив целых чисел `a`
// индекс начала подмассива `begin` и размер этого подмассива `n`,
// задающие подмассив, над которым необходимо провести разбиение
// индекс `j` его элемента `p = a[j]`

// выход:
// массив `a` изменен: в заданном его подмассиве сначала идут элементы,
// меньшие `p`, затем равные `p`, затем большие `p`
// структура borders_t с двумя полями left и right - соответственно
// наименьший и наибольший индексы элементов массива `a` после
// перестановки, равных p

void divide(std::vector<int>& a, int begin, int end, int j, int &left, int &right)
{
  int p = a[j];
  // элементы с индексами меньше left или больше right стоят
  // на правильных местах
  left = begin;
  right = end - 1;
  int i = begin;
  // на каждой итерации цикла мы либо увелечиваем `i`, либо уменьшаем right.
  // Поэтому, если в массиве `a` `n` элементов, цикл выполнится
  // ровно `n` раз
  while (i <= right)
  {
    if (a[i] < p)
    {
      // если i-й элемент меньше `p`, то помещаем его в левую часть
      // массива на "правильное" место
      // при этом элемент останется на том же месте, если элементов,
      // равных `p`, еще не было. В противном случае он заменит
      // собой элемент, равный `p`, либо элемент, который уже был
      // скопирован на "правильное" место
      int temp = a[left];
      a[left] = a[i];
      a[i] = temp;
      i++;
      left++;
    }
    else if (a[i] > p)
    {
      // если i-й элемент больше `p`, то обмениваем его местами с самым
      // правым непроверенным элементом
      // теперь элемент, который только что переставили вправо, стоит на
      // "правильном" месте, а элемент, переставленный влево, будет
      // проверен на следующей итерации
      int temp = a[right];
      a[right] = a[i];
      a[i] = temp;
      right--;
    }
    else if (a[i] == p)
    {
      // если i-й элемент равен `p`, то пропускаем его
      i++;
    }
  }
}
// вход:
// массив целых чисел `a`
// индекс начала подмассива `begin` и размер этого подмассива `n`,
// задающие подмассив, порядковую статистику которого нужно найти
// номер `k` порядковой статистики
// выход:
// `k`-я порядковая статистика заданного подмассива

int select(std::vector<int>& a, int begin, int end, int k)
{
  // выбираем индекс j случайно
  int j = begin + std::rand() % (end - begin);
  int left = begin;
  int right = end;
  // осуществляем разбиение заданного подмассива
  divide(a, begin, end, j, left, right);
  // в зависимости от того, в каком отрезке лежит искомая порядковая
  // статистика, вызвать select для подмассива или вернуть значение
  if (k < left)
  {
    return select(a, begin, left - 1, k);
  }
  else if (k <= right)
  {
    return a[k];
  }

  return select(a, right + 1, end, k);
}

int main()
{
  std::srand(std::time(nullptr));

  std::cout << "Input size: ";
  int n = 0;
  std::cin >> n;

  if (n < 1)
  {
    return -1;
  }

  std::vector<int> a;

  int val;
  for (int i = 0; i < n; i++)
  {
    std::cin >> val;
    a.push_back(val);
  }

  // считываем индекс j
  int j = 0;
  std::cin >> j;
  if (j < 0 || j >= n) return 1;
  int left = 0;
  int right = n;
  // вызываем "разделяющую" процедуру divide
  divide(a, 0, n, j, left, right);
  // выводим изменённый массив и индексы
  for (int element : a) std::cout << element << ' ';
  std::cout << '\n' << left << ' ' << right << '\n';

  int median = select(a, 0, n, n - n / 2 - 1);
  std::cout << "Median = " << median;
}