Рекурсивное получение k-го наименьшего элемента в массиве

Question

Рекурсивное получение k-го наименьшего элемента в массиве

Я пытаюсь «перевести» этот алгоритм из псевдокода, приведенного в моем учебнике. Моя программа продолжает падать, хотя, и я не совсем уверен, где я ошибся с моей реализацией. Вот псевдокод на изображении с моим кодом прямо под ним: введите описание изображения здесь

int kSmallFirst (int k, int anArray[], int first, int last) {
int pivotIndex = 0;

if (k < pivotIndex - first + 1)
return kSmallFirst(k, anArray, first, pivotIndex - 1);
else if (k == pivotIndex - first + 1)
return pivotIndex;
else
return kSmallFirst(k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last);
}

int main () {
int i = 0;
int arr[512];
fstream data;
data.open("data.txt");

while (!data.eof()) {
data >> arr[i];
i++;
}

data.close();

cout << kSmallFirst(42, arr, 0, i-1);

return 0;
}

Большое спасибо!

-1

algorithm arrays c++partition recursion

Решение

Другие решения

Обратите внимание, что kSmallFirst никогда не использует anArrayтак вопреки чему Jorio говорит, что это не проблема ввода. Даже если бы он попытался использовать диапазон main передает диапазон [0 .. -1] в виде kSmallFirst«s first а также last,

Вы должны понимать, что делает алгоритм, в противном случае, как указано CiaPan Вы не будете выполнять самую важную часть.

kSmall является:

Брали в раздел anArray определяется first а также last
Выбор pivotIndex в разделе anArray между first а также last
Перемещение всех элементов меньше чем anArray[pivotIndex] ниже pivotIndex и все элементы больше чем anArray[pivotIndex] выше pivotIndex
Это определит следующую пару разделов anArrayраздел от first в pivotIndex и раздел из pivotIndex в last
kSmall вернется на диапазон, который будет содержать kй элемент

Переписывание kSmall с учетом этого получим:

#include <algorithm>
#include <functional>

int kSmall(int k, int* anArray, int first, int last){
int p = anArray[(last - first) / 2 + first]; // Choose a pivot value from anArray[first .. last]
int* pivotIndex = std::partition(anArray + first, anArray + last, std::bind2nd(std::less<int>(), p)); // Partition the values of anArray around p

if(k < pivotIndex - anArray){
return kSmall(k, anArray, first, pivotIndex - anArray);
}
else if(k == pivotIndex - anArray){
return pivotIndex - anArray;
}
else{
return kSmall(k, anArray, pivotIndex - anArray, last);
}
}

Я уверен, что вы заметите, что математика в утверждении if отличается от книги. Я решил реализовать kSmall, как вы использовали int параметры, книга выбрала для использования int* параметры.

2

Вы выбрали неверное значение индекса индекса.

Поскольку это рекурсия, вам нужно обновлять сводку для каждого вызова.

Сделайте это более общим.

в функция kSmallFirst,

использование pivotIndex = первый, скорее, чем pivotIndex = 0.

0

Источник

Accepted Answer

Проблема в том, что у вас есть не реализована основная часть алгоритма, который описан в вашей книге с курсивный шрифт:

Выберите сводное значение ‘p’ form ‘anArray [first..last]’

Разделите значения ‘anArray [first..last]’ о ‘p’

Эти две строки не комментарий! Они псевдокод, который вы собираетесь перевести на C / C ++ чтобы ваш код делал то, что вы хотите.

4