Почему сравнения тратятся впустую при сортировке выбором?

Я читаю о сортировке выбором в книге Algorithms In A Nutshell. В книге появляется следующее:

Сортировка выбором является самым медленным из всех алгоритмов сортировки. Он многократно выполняет почти одну и ту же задачу, ничего не изучая от одной итерации к другой. Выбор самого большого элемента, max, в A требует n-1 сравнений, а выбор второго по величине элемента требует n-1 сравнений - не так много! Многие из этих сравнений напрасны, потому что если элемент меньше секунды, он не может быть самым большим элементом и, следовательно, не влияет на вычисление максимума.

Что означает текст, выделенный жирным шрифтом?

Может кто-нибудь объяснить на простом примере?


sorting algorithm selection-sort
person venkysmarty    schedule 07.11.2013    source источник
comment
Взгляните на bogosort, чтобы найти самый медленный алгоритм сортировки.   -  person this    schedule 07.11.2013
comment
Существует много гораздо более медленных алгоритмов сортировки, таких как богосортировка или сортировка марионеток. Сортировка выбором как раз эффективная (причина указана в цитате), а не самая медленная   -  person phuclv    schedule 07.11.2013
comment
Сортировка выбором может быть полезна для небольших массивов с небольшим сравнением и большой стоимостью подкачки.   -  person this    schedule 07.11.2013

Ответы (2)


arrow_upward
1
arrow_downward

Автор вашей книги, кажется, любит сложные, длинные предложения. Не учись этому у него; уже достаточно людей, умеющих запутать своих читателей.

Попытка упростить понимание:

Выбор самого большого элемента из A требует n-1 сравнений, когда A имеет n элементов. К сожалению, алгоритм сортировки не использует эту информацию повторно.

Когда он снова запускает внутренний цикл для сортировки оставшихся элементов, ему нужны еще n-2 сравнения (один элемент был отсортирован в нужное место в последнем цикле).

Поскольку сортировка перемещает только один элемент за один проход внутреннего цикла, большинство сравнений повторяются снова и снова, ничего не делая с результатом — это просто пустая трата времени.

В Википедии есть красивая анимация работы сортировки выбором.

person Aaron Digulla    schedule 07.11.2013

arrow_upward
0
arrow_downward

Рассмотрим 3,5,2,4,1.

Самый большой элемент 5. Второй по величине элемент — 4.

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

person Bernhard Barker    schedule 07.11.2013