Проблема с типами с использованием алгоритма быстрой сортировки

Question

У меня проблема с разными типами в реализации алгоритма быстрой сортировки с использованием шаблонов итератора, и я не могу понять, что происходит.

Алгоритм следующий:

template <typename I> void ordenacion_rapida(I i, I j, int n0=1) 
{ 
    int n = j-i; 

    if (n<=n0) 
     ordenacion_insercion<I>(i, j); 
    else 
    { 
     I p = pivote(i, j); 
     ordenacion_rapida<I>(i, p); 
     ordenacion_rapida<I>(p+1, j); 
    } 
} 

template <typename I> I pivote(I i, I j) 
{ 
    I p = i; 
    typedef typename iterator_traits<I>::value_type tipo; 
    tipo x = *(i); 

    for (I k=i+1; k<j; ++k) 
     if (*(k)<=x) 
     { 
      ++p; 
      tipo aux = *(p); 
      *(p) = *(k); 
      *(k) = aux; 
     } 
    *(i) = *(p); 
    *(p) = x; 
} 

template <typename I> void ordenacion_insercion(I i, I j) 
{ 
    typedef typename iterator_traits<I>::value_type tipo; 
    for (I k=i+1; k<j; ++k) 
    { 
     tipo x = *(k); 
     while (k!=i && x<*(k-1)) 
     { 
      *(k) = *(k-1); 
      --k; 
     } 
     *(k) = x; 
    } 
} 

Прости меня, если есть exccessive количество кода, но проблема может быть в любой строке, которую я исчерпывающе анализ.

Дело в том, что когда я пытаюсь сортировать vector<double или vector<float> Обнаружена ошибка, тогда как нет такой проблемы, когда я использую vector<int>.

Где проблема?

Answer 1

Я не вижу ничего плохого с вашим кодом, он отлично работает. Единственная проблема - вы забыли вернуть что-то внутри pivote.

#include <iterator> 
#include <vector> 
using namespace std; 

template <typename I> void ordenacion_insercion(I i, I j) 
{ 
    // snip 
} 

template <typename I> I pivote(I i, I j) 
{ 
    // snip 

    // Assuming you intended to return P 
    return p; 
} 

template <typename I> void ordenacion_rapida(I i, I j, int n0=1) 
{ 
    // snip 
} 

#include <iostream> 

int main() { 
    std::vector<double> v = { 1.2f, 0.5f, 3.5f, 0.2f }; 
    ordenacion_rapida(v.begin(), v.end()); 
    for (unsigned int i = 0; i < v.size(); i++) 
     std::cout << v[i] << " "; 
} // 0.2 0.5 1.2 3.5