Реализация сортировки на основе итератора
Мой вид оболочки выглядит так:
template<class T>
void shellSort(T *begin, T *end) {
int shell = 1;
while (shell < (begin - end) / 3) shell = shell * 3 + 1;
while (shell > 0) {
for (auto index = shell; index < end; index++) {
for (auto insertion = index; insertion >= shell && *(insertion - shell) > *(insertion); insertion -= shell) {
swap(*(insertion - shell), *(insertion));
}
}
shell = shell / 3;
}
}
Довольно бегать с мельницы. Проблема, с которой я сталкиваюсь, заключается в следующем:
for (auto index = shell; index < end; index++)
поскольку shell является int но end является int * он не знает, как сделать сравнение. Как мне решить эту проблему?
Решение
Используйте «итераторы» для адресации элементов и используйте целые числа только для относительных смещений:
for (auto index = begin + shell; index < end; ++index) ...
Кстати, вы, вероятно, хотите shell < (end - begin)/3не (begin - end),
Другие решения
Предполагая, что это итераторы произвольного доступа, в противном случае производительность будет довольно плохой.
Ты можешь использовать std::distance чтобы получить разницу между двумя итераторами. Вы также можете использовать std::advance добавить целое число в итератор.