quick sort in C++

Question

Я реализую алгоритм быстрой сортировки из книги алгоритмов Кормена (CLRS), но всегда запрашивает «смещение вне диапазона», и я не знаю, как его исправить. Вот мой код.

template<typename Iterator> 
void quick_sort(Iterator first, Iterator last) 
{ 
    if (last - first > 1) 
    { 
     auto pivot = partition(first, last); 
     quick_sort(first, pivot); 
     quick_sort(pivot + 1, last); 
    } 
} 

template<typename Iterator> 
Iterator partition(Iterator first, Iterator last) 
{ 
    auto pivot = last - 1; 
    auto less_end = first - 1; 
    for (auto iter = first; iter != pivot; ++iter) 
    { 
     if (*iter <= *pivot) 
     { 
      std::swap(*++less_end, *iter); 
     } 
    } 
    std::swap(*(less_end + 1), *pivot); 
    return less_end + 1; 
} 

Заранее благодарен!

Answer 1

Когда в вашем partition(), first равно begin() подстилающей последовательности, то:

auto less_end = first - 1; 

становится неопределенным поведением.

Это, вероятно, будет вашей проблемой. Если нет, используйте ваш отладчик, чтобы каждый раз вводить код в строку, пока ошибка не встречается, и используйте ваш отладчик, чтобы выяснить, где и почему вещи уходят с рельсов. Для этого нужен отладчик.

Answer 2

Как уже указывал Сэм Варшавчик в his answer, начиная с первого-первого является проблемой. Простейшее решение: просто переложить все это на один, то есть начать с first, пост- вместо Преинкремент и так далее .....

template<typename Iterator> 
Iterator partition(Iterator first, Iterator last) 
{ 
    auto pivot = last - 1; 
    auto less_end = first; 
    for (auto iter = first; iter != pivot; ++iter) 
    { 
     if (*iter <= *pivot) 
     { 
      std::swap(*less_end++, *iter); 
     } 
    } 
    std::swap(*(less_end), *pivot); 
    return less_end; 
} 

см http://rextester.com/JCDUL96865