Сортировка вставками с минимальым числом операций присваивания
Нужно отсортировать массив методом вставок (организовав алгоритм так, чтобы использовать минимальное количество операций присваивания), а также посчитать количество использованных операций сравнения и операций присваивания.
Тестовые данные:
- Массив из 7 элементов = {2 3 4 5 6 7 1}. Число операций сравнения и присваивания: 12 и 8 соответственно.
- Массив из 7 элементов = {7 1 2 3 4 5 6}. Число операций сравнения и присваивания: 17 и 18 соответственно.
- Массив из 5 элементов = {1 2 3 4 5}. Число операций сравнения и присваивания: 4 и 0 соответственно.
int n;
cin >> n;
vector<int> arr4(n)
for (int i = 0; i < n; i++)
{
cin >> arr4[i];
}
for (int i = 1; i < n; i++) {
int x = arr4[i];
for (j = i - 1; j >= 0 && arr4[j] > x; j--) {
arr4[j + 1] = arr4[j];
countEquals++;
}
countChecks += 2;
arr4[j + 1] = x;
countEquals += 2;
}
cout << countChecks << " " << countEquals << endl;
Программа работает неверно, что я делаю не так?
Примеры неверной работы:
- Входной массив (n = 7): {2 3 4 5 6 7 1}. Вывод: 6 18. Ожидалось: 12 8
- Входной массив (n = 7): {7 1 2 3 4 5 6}. Вывод: 6 18. Ожидалось: 17 18
- Входной массив (n = 5): {1 2 3 4 5}. Вывод: 4 8. Ожидалось: 4 0