Быстрая сортировка на C++ вектор


Я видел других реализаций, но они, кажется, довольно сложно. Это, кажется, работает для меня, но что я упускаю? Кроме того, какие-либо советы о том, как я могу улучшить качество кода приветствуется.

#include <iostream>
#include <vector>

template<typename Iter>
void quickSort(std::vector<typename Iter::value_type>& vec, Iter left, 
    Iter right) {

    auto size = std::distance(left, right);
    if (size <= 1) {
        return;
    }
    auto pivot = std::next(right, -1);
    if (size == 2 && *pivot < *left) {
        std::iter_swap(left, pivot);
    }
    auto wall = left;
    auto curr = left;

    while (curr != right) {
        if (*curr < *pivot) {
            std::iter_swap(wall, curr);
            wall++;
        }
        curr++;
    }

    std::iter_swap(pivot, wall);
    quickSort(vec, left, wall);
    quickSort(vec, wall + 1, right);

}

int main() {
    std::vector<int> myVec = { 6, 5, 2, 3, 2, 4, 34, 2434, 251, 4, 12, 4, 5,
        634, 523, 5, 4, 353, 3, 5, 345, 7, 86786, 8, 7, 9, 1 };
    quickSort(myVec, myVec.begin(), myVec.end());
    return 0;
}


2130
7
задан 8 марта 2018 в 03:03 Источник Поделиться
Комментарии
2 ответа


  • Вам не нужно проходить сам вектор. left и right итераторы предоставляют всю необходимую информацию.

    Что сказал, Вы передаете правильно rightслишком часто люди проходят его, как .end() - 1 что действительно приводит к ненужным осложнениям.


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

  • Линии

    if (size == 2 && *pivot < *left) {
    std::iter_swap(left, pivot);
    }

    не служат никакой цели. Код прекрасно работает без них.


  • Самая сложная часть-это достижение наилучшей производительности.


    • Бедных выбор оси может привести к квадратичной временной сложностью. В профессиональной реализации выберите Pivot - это самая сложная часть.

    • В общем, в C++ очень хорош в устранении хвостовую рекурсию, но в данном конкретном случае она может использовать некоторую помощь. В частности, вы хотели бы повторить на более мелкие секции, и перебрать большего.

    • Еще одним способом оптимизации является своевременное переключение для вставки рода. Вместо убывающей на всем пути к size <= 1 это выгодно, чтобы остановить рекурсию раньше (скажем, когда size <= 16). После того, как рекурсии будут завершены, ассортимент почти отсортирован, и вставки сортировки за линейное время.


4
ответ дан 8 марта 2018 в 05:03 Источник Поделиться

Дополнения к ВНП возьмем:


  • код должен быть документирован. Вы можете найти (и обосновать) (сжатый) презентации, как ваша, в печатных СМИ, где его не легко отделиться от объяснений в связи с программным кодом, там копировать и вставить. Язык программирования может или не может иметь стандарт для документирования назначение и пределы конструкции. Я не знаю таких Для "с-семье", я использую и рекомендую помощи Doxygen.

  • следует читать: templaterex' как реализовать классические алгоритмы сортировки в современном C++

  • ВНП подразумевается, что вы не хотите повторить в более крупные разделы
    это вопрос корректности даже больше, чем переживает (невыносимо) время выполнения квадратичного в число элементов для сортировки:
    в худшем случае, ты бы вложить один звонок за штуку, возможно, наезд ограничение на стекового пространства или глубина вложенности.

  • этот наихудший случай возникает, если выбирать pivot как показано на (почти) предварительно заказанные товары - плачевно, даже неприязненно частого использования.

  • уменьшить визуальное воздействие специальным кожухом:

    if (size < QUICK_LIMIT) {
    if (size <= 1) {
    return;
    auto other = std::next(left);
    if (2 == size && *other < *left) {
    std::iter_swap(left, other);
    return;
    }
    // handle 2 < size < QUICK_LIMIT
    }

2
ответ дан 8 марта 2018 в 09:03 Источник Поделиться