Ошибка в реализации сортировки

372

12 февраля 2017, 11:40

Если я правильно понял проблему, то она заключается в том, что я не ставлю некоторые числа на правильное место. Но я не знаю, как исправить эту проблему.

std::vector<int>::iterator partition(std::vector<int>::iterator left,
                                     std::vector<int>::iterator right, 
                                     int elem) {
    while (first!=last) {
while (pred(*first)) {
  ++first;
  if (first==last) return first;
}
do {
  --last;
  if (first==last) return first;
} while (!pred(*last));
swap (*first,*last);
++first;

} return first; }

Answer 1

elem никогда не выбирается последний
Нужно включить pivot в правый интервал, ведь он ещё не встал на своё место.
у тебя elem всегда попадает в левую часть, а pivot - это просто место встречи. После такого partition гарантируется только:

[0, pivot) <= elem
[pivot, last] > elem

В общем:

 void quicksort(std::vector<int>::iterator left, std::vector<int>::iterator right) {
    if (left >= right) {
        return;
    }
    auto elem = rand() % (right - left + 1) + left; // <- тут
    std::vector<int>::iterator pivot = partition(left, right, *elem);
    quicksort(left, pivot - 1);
    quicksort(pivot, right); // <- и тут
}

Я заинлайнил partition(более каноничный), может и не стоит его выделять?

void quicksort(std::vector<int>::iterator left, std::vector<int>::iterator right) {
    auto elem = rand() % (right - left + 1) + left;
    //
    auto i = left, j = right;
    while (i <= j) {
        while (*i < *elem) ++i;
        while (*j > *elem) --j;
        if (i <= j) std::swap(*i++, *j--);
    }
    //
    if (left < j)  quicksort(left, j);
    if (i < right) quicksort(i, right);
}