Уменьшение одним алгоритмом

Question

Если определение уменьшения на одну стратегию таково:

"Стратегия, при которой размер решаемой задачи постоянно уменьшается на один элемент на каждой итерации".

Означает ли это, что сортировка вставок не уменьшается на один алгоритм? Так как необходимо сравнить все элементы, которые уже были отсортированы, следовательно, требуется более одной итерации для сортировки каждого элемента.

Или определение будет относиться к тому факту, что оно перебирает каждый элемент, сортируя каждый по одному?

Answer 1

В соответствии с этим определением я бы сказал, что сортировка вставок не является алгоритмом понижения на единицу по той причине, о которой вы уже упоминали. То есть вы не можете вызвать метод сортировки вставкой после одного прохода алгоритма для меньшего подмножества данных, так как для вставки вам нужны все данные.

Я считаю, что определение не относится к тому факту, что "алгоритм выполняет итерацию по каждому элементу один за другим", как это делает большинство алгоритмов, использующих массивы, а скорее превращает проблему в меньшую подзадачу, которая может быть решена точно так же Кстати, но с меньшим количеством данных. Пузырьковая сортировка - это алгоритм уменьшения на единицу, поскольку при каждом проходе мы помещаем максимальный элемент на место, а затем выполняем пузырьковую сортировку для остальных. N-1 элементы точно так же.