Сортировка вставок, начиная с конца вектора

Question

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

Вот что у меня есть, но оно не работает (ошибка за пределами границ):

void sort(vector<double> &a) {
    for (int n = a.size() - 2; n >= 0; --n) {
        double aTemp = a.at(n);
        int i = n+1;
        while (i < a.size() - 1 && aTemp < a.at(i)) {
            a[i] = a[i + 1];
            ++i;
        }
        a[i+1] = aTemp;
    }
}

int main() {
    vector<double> a = {3, 2, 5, 8, 1, 9};
    sort(a);
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << ' ';
    }
    return 0;
}

Answer 1

Я предполагаю, что вы знаете о функции сортировки STL и просто экспериментируете с сортировкой вставкой.

Ваша логика по большей части верна.Единственная проблема, которую я обнаружил, состояла в том, что вы оставляли a[n] 'дыру' незаполненной и в худшем случае добавляли элементы в a[a.size()].

int i = n;
while (i <  a.size() - 1 && aTemp > a.at(i+1)) {
    a[i] = a[i + 1];
    ++i;
}
a[i] = aTemp;

Замена на эту решена проблема.