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 you have read our privacy policy.

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