std :: проблема с разделением сегментов - PullRequest
Новая
       15

std :: проблема с разделением сегментов

0 голосов
/ 15 октября 2018

Ради интереса я реализовал быструю сортировку, используя std::partition(), и получал ошибку.Я нашел пример реализации здесь , который немного отличался и работает.Несмотря на то, что я вижу преимущество в эффективности в их реализации, я не понимаю, почему у меня появляется ошибка.Единственное отличие состоит в том, что я не делаю секунду std::Partition, чтобы избежать передачи значений, которые совпадают с точкой поворота для последующих рекурсивных вызовов.Кто-нибудь может определить мою проблему? 

#include <algorithm>
#include <vector>
#include <iostream>

template <typename iter> void quick_sort(iter first, iter last)
{
    if ( std::distance( first, last ) <= 1 )
    {
        return;
    }

    auto pivot = *std::next( first, std::distance( first, last ) / 2 );

#if 0 //works
    iter midpoint1 = std::partition( first, last, [pivot](const auto& x)->bool{ return ( x < pivot ); } );
    iter midpoint2 = std::partition( midpoint1, last, [pivot](const auto& x)->bool{ return !( pivot < x ); } );
    quick_sort( first, midpoint1 );
    quick_sort( midpoint2, last );
#else //segfaults
    iter midpoint = std::partition( first, last, [pivot](const auto& x){ return ( x < pivot ); } );
    quick_sort( first, midpoint );
    quick_sort( midpoint, last );
#endif
}

int main()
{
    std::vector<int> to_sort = {2,1,7,4,6,9,2,1,5,8,9,4,7,4,3,7,4,8,3,8,9};

    quick_sort( std::begin( to_sort ), std::end( to_sort ) );

    for ( auto n : to_sort )
    {
        std::cout << n << ',';
    }

    std::cout << '\n' << std::flush;
}

1 Ответ

0 голосов
/ 15 октября 2018

Рассмотрим последовательность, в которой выбранная вами опорная точка является наименьшим элементом.

Тогда ваше разбиение приведет к пустой последовательности (где вы перестанете повторять) и к исходной.

Повтордо переполнения стека, или, с хвостовой оптимизацией, система изнашивается.

Кроме того, в коде, который вы говорите, работает, вы использовали большее > один раз, хотя вы должныиспользуйте только меньше <.

...