Какое количество свопов требуется при сортировке выбором для каждого случая?

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

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

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

Время выполнения сортировки выбором в лучшем и худшем случае равно n^2. Это связано с тем, что независимо от того, как изначально расположены элементы, на i-й итерации основного цикла for алгоритм всегда проверяет каждый из оставшихся n-i элементов, чтобы найти наименьший из оставшихся.

Сортировка выбором — это алгоритм, который использует минимальное количество свопов, и в лучшем случае он использует НУЛЬ (0) свопов, когда вход находится в отсортированном массиве, таком как 1,2,3,4. Но более уместен вопрос: каково наихудшее число свопов в сортировке выбором? И для какого входа это происходит?

Ответ: В худшем случае число свопов равно n-1. Но это не происходит только для противоположно упорядоченного ввода, скорее противоположно упорядоченный ввод, такой как 6,5,3,2,1, не требует наихудшего количества свопов, а требует n/2 свопов. Так что же на самом деле представляет собой вход, для которого количество свопов занимает N-1 свопов? Если вы проанализируете немного больше, вы увидите, что наихудший случай возникает для «СИНУСОВОЛННОГО ВИДА ВХОДА». Это альтернативное увеличение и уменьшение входа, так же как гребень и впадина.

7 6 8 5 9 4 10 3 - ввод восьми (8) элементов потребует 7 перестановок

3 6 8 5 9 4 10 7 (1)

3 4 8 5 9 6 10 7 (2)


3 4 5 8 9 6 10 7 (3)


3 4 5 6 9 8 10 7 (4)

3 4 5 6 7 8 10 9 (5)

3 4 5 6 7 8 10 9 (6)

3 4 5 6 7 8 9 10 (7)

Следовательно, доказано, что наихудший случай количества свопов в сортировке выбором равен n-1, лучший случай — 0, а средний — (n-1)/2 свопа.