#include <iostream>
#include <cstdlib>

void swap(int *A, int, int);

void bubbleSort(int *A, int start, int end)
{
  for (int endPass = end - 1; endPass >= start; endPass--)
    for (int left = start; left <= endPass; left++)
      if (A[left] > A[left + 1])
	swap(A, left, left + 1);
}

/**
 * Moves the median of A[start]...A[end] into A[start].
 */

void findMedian(int *A, int start, int end)
{
  bubbleSort(A, start, end);
  swap(A, start, (start + end) / 2);
}

void swap(int *A, int from, int to)
{
  int temp = A[from];
  A[from] = A[to];
  A[to] = temp;
}

/**
 * Returns the element of rank i from A[p],...,A[r].
 *
 * @param A an array of integers
 * @param i the rank to return (1 for smallest)
 * @param p the first index in the array to consider
 * @param r the last index in the array to consider
 * @return the element of rank i
 */

int select(int *A, const int i, const int p, const int r)
{
  if (r - p + 1 <= 5)
    {
      bubbleSort(A, p, r);
      return A[p + i - 1];
    }

  int numInputs = r - p + 1;
  int numGroups = numInputs / 5;
  if (numInputs % 5 != 0)
    numGroups++;

  for (int g = 0; g < numGroups; g++)
    {
      findMedian(A, g * 5, (g * 5 + 4 < r ? g * 5 + 4 : r));
    }

  for (int g = 1; g < numGroups; g++)
    {
      swap(A, g, g * 5);
    }

  int x = select(A, (numGroups + 1) / 2, 0, numGroups - 1);

  int lastSmall = p - 1;

  for (int k = p; k <= r; k++)
    {
      if (A[k] <= x)
	{
	  lastSmall++;
	  swap(A, k, lastSmall);
	}
    }

  if (i <= lastSmall + 1)
    {
      return select(A, i, p, lastSmall);
    }
  else
    {
      return select(A, i - (lastSmall + 1), lastSmall + 1, r);
    }
}

int main()
{
  int n;

  std::cout << "Enter n" << std::endl;
  std::cin >> n;

  // make array holding 1,...,n

  int *A = new int[n];
  for (int i = 0; i < n; i++)
    A[i] = i + 1;
 
  // randomly permute the array

  for (int i = 0; i < n; i++)
    swap(A, random() % n, random() % n);

  int rank;
  std::cout << "Enter rank to find" << std::endl;
  std::cin >> rank;
  
  std::cout << select(A, rank, 0, n - 1) << std::endl;
}