0

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

std::vector<int>::iterator partition(std::vector<int>::iterator left,
                                     std::vector<int>::iterator right, 
                                     int elem) {
    // Проверка вроде как бесполезная, но все же поставил
    if (left == right) {
        return left;
    }
    while (left != right) {
        // двигаю левый итератор до того момента, пока он меньше elem
        while (*left < elem) {
            ++left;
            if (left == right)
                return left;
        }
        // Двигаю правый итератор, пока он меньше elem. 
        // Проблема скорее всего здесь, так как случай равенства elem не обрабатывается
        while (*right > elem) {
            --right;
            if (right == left)
                return right;
        }
        // Если итераторы не совпали, значения итераторов меняются и цикл продолжается
        if (left != right) {
            std::swap(*left, *right);
            ++left;
        }
    }
    return left;
}


void quicksort(std::vector<int>::iterator left, std::vector<int>::iterator right) {
    if (left >= right) {
        return;
    }
    // Выбираю рандомный элемент из массива
    auto elem = rand() % (right - left) + left;
    // Соответственно опорный элемент, относительно которого массив будет делиться на части
    std::vector<int>::iterator pivot = partition(left, right, *elem);
    // Рекурсивные вызовы. Возможно, проблему можно исправить здесь, делая 
    // std::swap(elem, pivot) и quickosort(left, pivot). То есть элемент, 
    // относительно которого все раскидалось будет в конце и массив поделиться относительно elem'a.
    quicksort(left, pivot - 1);
    quicksort(pivot + 1, right);
}

int main() {
    size_t N = 0;
    std::cin >> N;
    std::vector<int> array(N);
    for (size_t i = 0; i != N; ++i) {
        std::cin >> array[i];
    }
    if (N != 0)
        quicksort(array.begin(), array.end() - 1);
    for (auto elem : array) {
        std::cout << elem << " ";
    }
}

Например:

7

7 7 7 -1 3 -1 -1 -> -1 -1 -1 7 3 7 7 (не понимаю, почему 3 оказалась именно там)

Или

6

-4 2 3 1 4 3 -> -4 1 3 2 3 4

8
  • В partition() после swap добавьте еще и --right. / А для эффективности (как мне кажется) можно еще перед вызовом partition поменять случайный elem со средним в массиве.
    – avp
    10 фев 2017 в 15:07
  • @avp я специально убрал этот момент, так как right может уйти левее left и будет бесконечный цикл.
    – Alexander
    10 фев 2017 в 15:16
  • 1
    А, только сейчас заметил != -- обычно там пишут whilе (left <= right). Да и циклы, в которых сдвигают left и right, стараются делать максимально короткими. Впрочем, лучше посто посмотрите нормальное (например, как у Кнута) описание алгоритма с его анализом, как правильно выбирать pivot и в каком порядке сортировать подмассивы после выбора pivot и почему тут лучше делать итерацию, а не рекурсию и т.д. и т.п.
    – avp
    10 фев 2017 в 15:32
  • Вот здесь quicksort(pivot + 1, right); тоже ошибка. Нужно quicksort(pivot, right);.
    – avp
    10 фев 2017 в 15:52
  • 3
    Значит для случая left == right в partiton() надо возвращать left + 1 / И еще момент, вот тут auto elem = rand() % (right - left) + left; выбирается elem из отрезка без последнего элемента. left -- первый, right -- последний, значит количество элементов = right - left + 1
    – avp
    10 фев 2017 в 16:10

1 ответ 1

2
  1. elem никогда не выбирается последний
  2. Нужно включить 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);
}
2
  • ваша реализация хороша, но не очень понятно, почему он должен возвращать два итератора. Мой инвариант partition - это то, что слева от отправленного elem все элементы меньше, а справа больше. Разве это не гарантирует того, что массив поделится и будет уменьшаться на части? (Скорее всего я что-то не понимаю).
    – Alexander
    10 фев 2017 в 17:02
  • Массив-то поделится, но вот только не совсем так, как ожидается. Я описал в пункте 2 поведение.
    – vp_arth
    10 фев 2017 в 19:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.