C++ generic insertion sort

Question

Я создаю это, чтобы лучше понять алгоритмы сортировки и общие функции. Я реализовал базовый алгоритм сортировки вставки, и я пытаюсь заставить его работать с несколькими структурами данных (списки и массивы, по крайней мере).

Поскольку я могу получить доступ к таким спискам: list [N], чтобы получить значение, я думаю, что мне нужно использовать итераторы. Поэтому я пытаюсь преобразовать свое решение. Вот основная вставка рода алгоритм Я пытаюсь изменить:

int *insertionsort(int *a) 
{ 
    for (int i = 1; i<length(a); ++i) 
    { 
    int k = a[i]; 
    int j = i-1; 
    { 
     while (j>=0 && a[j] > k) 
     { 
     a[j+1] = a[j--]; 
     } 
    a[j+1] = k; 
    } 
    return a; 
} 

А вот то, что я до сих пор для общей версии:

template <class T> 
T insertionsort(T a) 
{ 
    for (auto i = a.begin()+1; i<a.end(); ++i) 
    { 
    auto k = i; 
    auto j = i-1; 
    while (j>=a.begin() && *j>*k) 
    { 
     (j + 1) = j--; 
    } 
    (j + 1) = k; 
    } 
    return a; 
} 

Unfortunatley Я не могу показаться, чтобы получить это родовое функция для правильной сортировки. Я смотрел на это довольно долго, не повезло. Идеи?

Answer 1

Размещено только для ссылки ОП и вряд ли будет жить долго. Если вы так склонны использовать C++ 11 и не хотите печатать, это может сделать трюк.

template<typename Iter> 
void insertion_sort(Iter first, Iter last) 
{ 
    for (Iter it = first; it != last; ++it) 
     std::rotate(std::upper_bound(first, it, *it), it, std::next(it)); 
} 

Relavent ссылки для функций, используемых:

std::upper_bound, std::next и std::rotate. Наслаждаться.

Answer 2

Я думаю, что вы путаетесь с разыменованием итераторов/указателей. Это должно работать:

template <class T> 
T insertionsort(T a) 
{ 
    if(a.begin() == a.end()) // return a when it's empty 
     return a; 
    for(auto i = a.begin() + 1; i < a.end(); ++i) 
    { 
     auto k = *i; // k is the value pointed by i 
     auto j = i - 1; 
     while(j >= a.begin() && *j > k) 
     { 
      *(j + 1) = *j; // writen in 2 lines for clarity 
      j--; 
     } 
     *(j + 1) = k; 
    } 
    return a; 
} 

Answer 3

Ее лучше, для более общего решения, чтобы передать диапазон, который будет отсортирован вместо вещей, чтобы быть отсортированы, так как стандартные алгоритмы, такие как std::sort() сделать:

template <typename BIDIRECTIONAL_ITERATOR> 
void insertionsort(BIDIRECTIONAL_ITERATOR begin , BIDIRECTIONAL_ITERATOR end) //Note that the iterators 
{                    //are passed by value 
    if(begin == end) return; //If the range is empty, abort 

    for(auto i = begin + 1; i < end; ++i) 
    { 
     auto j = i - 1; 
     bool flag = false; //Used to abort the loop after j == begin case 
     while(!flag && (j != begin || (flag = j == begin)) && *j > *i) 
     { 
      *(j + 1) = *j; 
      j -= !flag; //If j == begin, don't decrement (Without branch) 
     } 
     *(j + 1) = *i; 
    } 
} 

Функция - это процедура, не возвращает ничего, сортирует исходный диапазон.