§. ПМ Число шагов сортировки выбором
В этом массиве из 8 элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из N элементов такая операция будет проводиться N − 1 раз. Объясните почему.
Решение
При сортировке выбором после первого выбора наибольший элемент ставится на место A[]. На этом месте он уже окончательно расположен, поэтому остаётся N − неупорядоченный элемент. После второго выбора окончательно расположен и A[]; остаётся N − элемента. После выбора для позиции i упорядочены первые i элементов, а неупорядоченных остаётся N − i. Когда выбор сделан для позиции N − , остаётся один элемент A[N]. Его не с чем сравнивать и некуда переставлять: он уже занимает последнее свободное место. Следовательно, выбор выполняется для позиций , , …, N − , то есть N − раз. Для примера из книги N = , и число выборов равно − = . Если написать цикл до N, последняя его итерация только выберет A[N] и обменяет элемент с самим собой; это лишняя операция.
Ответ
Достаточно N − выборов: после размещения первых N − элементов последний занимает единственное оставшееся место.
