Ошибка в QVector<T>:: operator []: неожиданно выброшен "индекс вне диапазона"

У меня есть два метода сортировки: сортировка вставкой и сортировка оболочки. Две из этих рабочих функций я адаптировал к 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]; }

1 ответ

Решение

В условии цикла for есть смысл проверить значение j перед сравнением элементов:

for (int j = i; j >= h && less(arr, j, j-h); j -= h)
Другие вопросы по тегам