Сортировка прямого выбора против сортировки обмена

Question

В чем разница между сортировкой прямого выбора и сортировкой выбора выбора ? Сегодня я вступил в небольшую дискуссию - мой профессор использует эти две терминологии в своих конспектах лекций. Сортировка выбора, которую вам даст Википедия и любой учебник или веб-сайт, - это то, что он называет «сортировкой выбора для обмена».

Я никогда не слышал ранее использовавшегося термина «сортировка выбора по обмену» (только «сортировка по выбору») и не могу найти в Интернете никаких релевантных ресурсов по предыдущей терминологии. Кроме того, «сортировка по обмену» перенаправляет на сортировку по пузырькам в Википедии.

Я также никогда не слышал ранее использовавшегося термина "сортировка по прямому выбору" и не могу найти в Интернете никаких подходящих ресурсов. В его заметках говорится, что это версия сортировки выбора, которая использует вторичный массив, а не сортировку по месту, заполняя его один за другим от наименьшего к наибольшему элементу. Когда я поднял вопрос, он утверждал, что он старше, и это только потому, что это не появляется в Google, не означает, что это неправильно. Тем не менее, я обнаружил в Google гораздо более неясные вещи, и что-то вроде сортировки будет иметь огромное количество ресурсов в Интернете.

Итак, эти алгоритмы идут под другими именами? У него просто неправильные имена? Кто прав?

Answer 1

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

Если вы создаете отсортированную копию списка, вы можете создать каждый элемент в новом списке один- одним из минимума старого списка;«Прямое» описание выглядит вполне разумно, как и любое другое.

OTOH Если вы сортируете список на месте, то каждый раз, когда вы перемещаете новый элемент в начало списка, вы должны перемещатьпредмет, который раньше был там назад, чтобы освободить место.В списке массивов самый дешевый способ сделать это - просто оставить новый минимальный элемент и поменять местами старый элемент: обмен.(В связанном списке было бы быстрее позволить всему хвосту списка скользить назад на одно место.)

Учебники, как правило, концентрируются на сортировке на месте.