У меня есть два метода сортировки: сортировка вставкой и сортировка оболочки. Две из этих рабочих функций я адаптировал к C ++ из простого C. Проблема в том, что функция ins_sort работает просто хорошо, а shell_sort завершается ошибкой. Какая причина для этого может быть?
bool less(QVector<int> &arr, int a, int b)
{
return arr[a] < arr[b];
}
// Performs swap on elements at a and b in QVector<int> arr
void qswap(QVector<int> &arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/* Failure is thrown in this method */
void shell_sort(GraphicsView &window, SwapManager &manager)
{
auto list = window.items();
QVector<int> arr;
for (auto item : list)
arr.push_back(static_cast<QGraphicsRectWidget*>(item)->m_number);
int N = arr.size();
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1)
{
for (int i = h; i < N; ++i)
{
for (int j = i; less(arr, j, j-h) && j >= h; j -= h)
{
qswap(arr, j, j-h);
manager.addPair(j, j - h);
}
}
h /= 3;
}
}
И это хорошо.
/* This method works just fine */
void ins_sort(GraphicsView &window, SwapManager &manager)
{
auto list = window.items();
int i, j;
QVector<int> arr;
for (auto item : list)
{
arr.push_back(static_cast<QGraphicsRectWidget*>(item)->m_number);
}
int N = arr.size();
for (i = 1; i < N; ++i)
{
for (j = i - 1; j != -1 && less(arr, j + 1, j); --j)
{
qswap(arr, j, j + 1);
manager.addPair(j, j + 1);
}
}
}
Отладчик указывает на этот кусок кода в «qvector.h»
Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
return data()[i]; }
В условии цикла for есть смысл проверить значение j до сравнивая предметы:
for (int j = i; j >= h && less(arr, j, j-h); j -= h)
Других решений пока нет …