Алгоритм разбиения Hoare — строгие или не строгие неравенства?
Мне действительно тяжело с реализацией алгоритма разбиения Хоара. По сути, я хочу разделить массив на две части, первая из которых содержит числа, меньшие заданного xи другой, содержащий большее. Тем не менее, я просто не могу найти хорошую реализацию. Это мой код:
void hoare(vector<int>&arr,int end, int pivot)
{
int i = 0;
int j = end;
while (i < j)
{
while (arr[i] < pivot)
i += 1;
while (arr[j] > pivot)
j -= 1;
swap(arr[i],arr[j]);
}
// return arr;
for (int i=0; i<end; i++)
printf("%d ", arr[i]);
}
Теперь я узнал, что множество сайтов имеют время (arr[i] <= pivot) вместо того, что я положил там. Тем не менее, когда я делаю это, для массива, как это:
1 3 5 7 9 2 4 6 8
Я получил:
1 3 5 4 9 2 7 6 8
Но опять же, в моей версии, для такого набора:
12 78 4 55 4 3 12 1 0
программа зависает, потому что, поскольку ни одно из условий во внешнем цикле не выполняется, оно просто проходит через это снова и снова, без приращения j или же i,
Пивот — это указатель на конкретное число в массиве, считая от 1; например, число 3, переданное функции в первом примере, будет означать pivot равняется arr[2]5
Извините, если это нубский вопрос или на него уже дан ответ, но я потратил на это целый день (также искал в сети решение) безрезультатно, и теперь у меня возникают мысли о самоубийстве.
Заранее спасибо.
Решение
Простой ответ на последовательность последовательности, конечно, использовать
auto it = std::partition(vec.begin(), vec.end(),
std::bind2nd(std::less<int>(), pivot));
Функция на самом деле не заботится о предикате, но переупорядочивает последовательность в две последовательности: одну, для которой предикат дает true и тот, для которого предикат дает false, Алгоритм возвращает итератор в конец первой подпоследовательности (состоящей из элементов, для которых предикат true). Интересно, что алгоритм должен работать на прямых итераторах (если он действительно получает прямые итераторы, он может использовать довольно много перестановок). Алгоритм, который вы реализуете, явно требует двунаправленных итераторов, то есть я проигнорирую требование также работать для прямых последовательностей.
Я бы использовал точно такой же интерфейс при реализации алгоритмов, потому что абстракция итератора очень хорошо работает для алгоритмов последовательности. Сам алгоритм просто использует std::find_if() найти итератор it В диапазоне [begin, end) такой, что предикат не содержит:
it = std::find_if(begin, end, not1(pred));
Если такой итератор существует, он использует std::find_if() искать в [std::reverse_iterator<It>(end), std::reverse_iterator<It>(it)) для итератора rit такой, что предикат действительно имеет место:
rit = std::find_if(std::reverse_iterator<It>(end), std::reverse_iterator<It>(it),
pred);
Если такой итератор существует, он std::swap()соответствующие местоположения и обновления begin а также end соответственно:
std::swap(*it, *rit);
begin = ++it;
end = (++rit).base();
Если либо it или же rit не найден, алгоритм завершается. Ввод этой логики в последовательный алгоритм кажется довольно простым. Обратите внимание, что этот алгоритм не может даже использовать оператор, который вы пытаетесь использовать, то есть концептуально элементы можно сравнивать только для x < pivot а также x >= pivot (который идентичен !(x < privot)).
Реализация ниже не проверена, но полный алгоритм будет выглядеть примерно так:
template <typename BiIt, typename Pred>
BiIt partition(BiIt it, BiIt end, Pred pred) {
typedef std::reverse_iterator<BiIt> RIt;
for (RIt rit(end);
(it = std::find_if(it, end, std::not1(pred))) != end
&& (rit = std::find_if(RIt(end), RIt(it), pred)) != RIt(it);
++it, end = (++rit).base()) {
std::swap(*it, *rit);
}
return it;
}
Другие решения
Других решений пока нет …