2016-05-01 14 views
0

Ich implementiere den schnellen Sortieralgorithmus aus Cormen's Algorithm Buch (CLRS), aber es immer "Offset außerhalb des Bereichs", und ich weiß nicht, wie es zu beheben. Hier ist mein Code.schnelle Sortierung in C++

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; 
} 

Vielen Dank im Voraus!

Antwort

1

Wenn in Ihrem partition() ist first zum begin() der zugrunde liegenden Sequenz gleich ist, dann:

auto less_end = first - 1; 

undefiniertes Verhalten wird.

Dies ist wahrscheinlich Ihr Problem. Wenn nicht, verwenden Sie Ihren Debugger, um den Code Zeile für Zeile durchzugehen, bis der Fehler auftritt, und verwenden Sie Ihren Debugger, um herauszufinden, wo und warum die Dinge nicht mehr funktionieren. Dafür ist ein Debugger zuständig.

0

Wie Sam Varshavchik bereits in his answer hingewiesen hat, ist bei 1 beginnend das Problem. Einfachste Lösung: Verschiebung nur die ganze Sache nach dem anderen, das heißt bei first beginnen, post- statt Pre-Zuwachs und so weiter .....

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

sehen