Почему сортировка вставок «уменьшается и побеждает», а сортировка «грубая сила»?

Question

Почему алгоритмы сортировки вставками также не считаются алгоритмами перебора? Разве они не систематически просматривают все значения массива? Я предполагаю, что сортировка выбора имеет худшую временную сложность в лучшем случае, но я до сих пор не до конца понимаю различие между алгоритмом грубой силы и алгоритмом убывания и завоевания. Извините, если это глупый вопрос. Спасибо!

Answer 1

И вставку, и сортировку выбора можно назвать «уменьшением и завоеванием», потому что на каждом шаге внешнего l oop они обрабатывают все меньшую и меньшую часть массива.

Формально говоря, в этих родах loop invariant condition is that the subarray A[0 to i-1] is always sorted.

Я не встречал термин "грубая сила" в применении к алгоритмам сортировки, это выглядит чепухой. Алгоритмы грубой силы обычно проверяют все возможные варианты и выбирают лучший. Можно сгенерировать все перестановки массива или списка и выбрать отсортированную - этот вид sortinh можно назвать «глупой сортировкой» или что-то вроде .