K-th order statistics. What is the problem?

Question

C++ / C#

Good evening. Wrote a program to search for the K-th order statistics, based on the quicksort algorithm. The program gives the wrong answer on the 8th test. What could be the problem?

Task

Дан массив из n элементов. Какое число k-ое в порядке возрастания в этом массиве?

Формат входного файла
В первой строке входного файла содержатся два числа n размер массива и
k.(1 <= k <= n <= 3 * 10^7). Во второй строке находятся числа A, B, C, a1, a2 по модулю не
превосходящие 10^9. Вы должны получить элементы массива начиная с третьего по формуле:
a[i] = A * a[i-2] + B * a[i-1] + C. Все вычисления должны производится в 32 битном знаковом типе,
переполнения должны игнорироваться.

Формат выходного файла
Выведите k-ое в порядке возрастания число в массиве a.

My code:

#include <iostream>
#include <fstream>

int partition(int l, int h, int* array)
{
  int i = l, j = h;
  int pivot = array[l];
  while (i < j)
  {
    do {
      i++;
    } while (array[i] <= pivot);
    do {
      j--;
    } while (array[j] > pivot);                       
    if (i < j)
      std::swap(array[i], array[j]);
  }
  std::swap(array[j], array[l]);
  return j;
}

int quick_sort(int l, int h, int* array, int k)
{
  int pivot_index;
  if (l < h)
  {

    pivot_index = partition(l, h, array);
    if (k < pivot_index)
      quick_sort(l, pivot_index, array, k);
    else
      quick_sort(pivot_index + 1, h, array, k);
  }
  return array[k];
}


int main()
{
  std::ifstream fin;
  fin.open("kth.in");
  std::ofstream fout;
  fout.open("kth.out");

  int size, k;
  fin >> size >> k;
  int A, B, C;
  fin >> A >> B >> C;
  int* array = new int[size];
  fin >> array[0] >> array[1];
  for (int i = 2; i < size; i++)
  {
    array[i] = A * array[i - 2] + B * array[i - 1] + C;
  }

  fout << quick_sort(0, size, array, k-1);

  fin.close();
  fout.close();
  return 0;
}

Answer 1

You have some strange scheme in partition.
Imagine you have an array of 2 elements and the first is greater than the second (a[0] = pivot > a[1]).
Before the loop l = 0, h = 2, i = 0. Then in the first while you do i++. Then you compare a[i] with pivot in the first while. a[1] < pivot by assumption, so you make i = 2. That's it - you've already gone beyond the array.
Rewrite with the standard Hoare or Lomuto partitioning scheme .
Or you will have to add all sorts of conditions i < j everywhere, but I'm not sure.