Проблема программирования сортировки раздела

Question

Мне нужен алгоритм для выбора самого большого или наименьшего значения для k. Значения будут ints. Мой инструктор сказал мне использовать модифицированный алгоритм разбиения, чтобы найти наибольшее или наименьшее значение для k. Есть предположения?

Answer 1

Ниже приведено описание алгоритма quickselect. Я предполагаю, что вы хотите найти самое маленькое значение.

1. Возьмите первый элемент вашего массива. Это будет вашим стержнем. Следите за своим положением.

2. Разделите массив на основе этого стержня. Элементы, меньшие, чем ваш стержень, идут до вашего стержня в массиве; больше, после вашего стержня. (Этот шаг перемещает ваш стержень. Следите за его положением в вашем массиве.)

3. Теперь вы знаете, что ваш стержень больше pivot_position Количество элементов. Поэтому ваш стержень - это самый маленький элемент (pivot_position + 1).

   • Если к равно pivot_position + 1, то вы нашли свой к ое наименьшее значение. Поздравляем, возвращаем pivot_position в качестве позиции этого значения в массиве.

   • Если k составляет менее pivot_position + 1, вы хотите, чтобы какое-то значение было меньше вашего стержня. Посмотрите в части массива перед вашей точкой поворота для наименьшего значения для k.

   • Если k больше pivot_position + 1, вы хотите, чтобы какое-то значение было больше вашего стержня. Посмотрите в части массива после вашего поворота для наименьшего значения * k - (pivot_position + 1) * th (поскольку эта часть массива исключает наименьшие значения (pivot_position + 1)).

Поскольку вы используете C++, вероятно, вы должны реализовать свои функции следующим образом:

int select(int *array, int left, int right, int k); 
int partition(int *array, int left, int right, int pivot_position); 

select принимает ваш массив, левую и правую границы, и ваш K. Для уточнения, array[left] будет первым элементом; array[right] будет последним; right - left + 1 будет длиной массива. select возвращает позицию k th наименьший элемент.

partition принимает ваш массив, левую и правую границы и начальную позицию вашего стержня. Безопасно просто передавать 0 для pivot_position каждый раз, что означает, что вы хотите использовать первый элемент в массиве в качестве точки опоры. (В вариации, называемой randomized quickselect, вы выбираете случайный pivot_position.) partition возвращает положение точки опоры после того, как вы закончите движение вокруг.

Answer 2

STL имеет функцию partial_sort, которая сортирует первые k элементов последовательности и позволяет вам захватить этот элемент простым поиском.

Другими словами, найдите std::partial_sort, а остальное будет очевидно.

В STL есть также функция nth_element. Я уверен, что вы можете понять, как его использовать.