Выборочная сортировка - Selection sort

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Май 2019) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

Пример

Вот пример этого алгоритма сортировки пяти элементов:

Анимация сортировки выделения. Красный - текущий мин. Желтый - отсортированный список. Синий - текущий элемент.

(Кажется, что в этих двух последних строках ничего не изменилось, потому что последние два числа уже были в порядке.)

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

arr [] = 64 25 12 22 11 // Найдите минимальный элемент в arr [0 ... 4] // и поместите его в начало 11 25 12 22 64 // Найдите минимальный элемент в arr [1 ... 4] // и поместите его в начало arr [1 ... 4] 11 12 25 22 64 // Найдите минимальный элемент в arr [2 ... 4] // и поместите его в начало arr [2 ... 4] 11 12 22 25 64 // Найдите минимальный элемент в arr [3 ... 4] // и поместите его в начало arr [3 ... 4] 11 12 22 25 64 

Реализации

Ниже представлена ​​реализация в C. Больше реализаций можно найти на страница обсуждения этой статьи в Википедии.

 1 / * от [0] до [aLength-1] - это массив для сортировки * / 2 int я,j; 3 int aLength; // инициализируем длину a 4  5 / * продвигаем позицию по всему массиву * / 6 / * (мог бы сделать i  7 за (я = 0; я < aLength-1; я++) 8 { 9     / * находим элемент min в несортированном a [i .. aLength-1] * /10 11     / * предполагаем, что min является первым элементом * /12     int jMin = я;13     / * проверяем элементы после i, чтобы найти наименьший * /14     за (j = я+1; j < aLength; j++)15     {16         / * если этот элемент меньше, то это новый минимум * /17         если (а[j] < а[jMin])18         {19             / * найден новый минимум; запомнить его индекс * /20             jMin = j;21         }22     }23 24     если (jMin != я) 25     {26         замена(а[я], а[jMin]);27     }28 }

Сложность

Сортировку выбора нетрудно анализировать по сравнению с другими алгоритмами сортировки, поскольку ни один из циклов не зависит от данных в массиве. Для выбора минимума требуется сканирование ${displaystyle n}$ элементы (принимая ${displaystyle n-1}$ сравнения), а затем переставив его в первую позицию. Чтобы найти следующий самый низкий элемент, необходимо сканировать оставшиеся ${displaystyle n-1}$ элементы и так далее. Таким образом, общее количество сравнений равно

${Displaystyle (п-1) + (п-2) + ... + 1 = сумма _ {я = 1} ^ {п-1} я}$

К арифметическая прогрессия,

${displaystyle sum _ {i = 1} ^ {n-1} i = {frac {(n-1) +1} {2}} (n-1) = {frac {1} {2}} n (n -1) = {гидроразрыв {1} {2}} (n ^ {2} -n)}$

что является сложным ${displaystyle O (n ^ {2})}$ по количеству сравнений. Для каждого из этих сканирований требуется одна замена для ${displaystyle n-1}$ элементы (последний элемент уже на месте).

Сравнение с другими алгоритмами сортировки

Среди алгоритмов квадратичной сортировки (алгоритмы сортировки с простым средним случаем Θ (п²) ) сортировка выборкой почти всегда превосходит пузырьковая сортировка и гномья сортировка. Вставка сортировки очень похож в том, что после k-я итерация, первая k элементы в массиве отсортированы. Преимущество сортировки вставкой состоит в том, что она сканирует ровно столько элементов, сколько необходимо для размещения k + 1-й элемент, в то время как сортировка выбора должна сканировать все оставшиеся элементы, чтобы найти k + 1-й элемент.

Простой расчет показывает, что сортировка вставкой обычно выполняет примерно вдвое меньше сравнений, чем сортировка по выбору, хотя она может выполнять столько же или гораздо меньше в зависимости от порядка, в котором находился массив до сортировки. Это можно рассматривать как преимущество для некоторых в реальном времени приложения, в которых сортировка по выбору будет выполняться одинаково независимо от порядка в массиве, в то время как время выполнения сортировки вставкой может значительно различаться. Однако чаще это дает преимущество сортировки вставкой, поскольку она работает намного эффективнее, если массив уже отсортирован или «близок к отсортированному».

В то время как сортировка выбора предпочтительнее сортировки вставкой с точки зрения количества записей (Θ (п) свопы против Ο (п²) свопы), оно почти всегда намного превышает (и никогда не превосходит) количество операций записи, которые циклическая сортировка составляет, так как циклическая сортировка теоретически оптимальна по количеству записей. Это может быть важно, если запись значительно дороже чтения, например, с EEPROM или же Флэш-память, где каждая запись сокращает срок службы памяти.

Наконец, сортировка по выбору значительно превосходит большие массивы на Θ (п бревноп) алгоритмы разделяй и властвуй Такие как Сортировка слиянием. Однако сортировка вставкой или сортировка по выбору обычно быстрее для небольших массивов (то есть менее 10–20 элементов). На практике полезной оптимизацией рекурсивных алгоритмов является переключение на сортировку вставкой или сортировку по выбору для «достаточно маленьких» подсписок.

Варианты

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

Двунаправленный вариант сортировки выбора (иногда называемый коктейль из-за его сходства с вариантом пузырьковой сортировки коктейльный шейкер сортировка ) - это алгоритм, который на каждом проходе находит как минимальное, так и максимальное значения в списке. Это сокращает количество сканирований входных данных в два раза. Каждое сканирование выполняет три сравнения для двух элементов (сравнивается пара элементов, затем больший сравнивается с максимумом, а меньший - с минимумом), что на 25% меньше по сравнению с обычной сортировкой с выбором, при которой выполняется одно сравнение для каждого элемента. Иногда это сортировка с двойным выбором.

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

в бинго сортировка Вариант, элементы упорядочиваются путем многократного просмотра оставшихся элементов, чтобы найти наибольшую ценность, и перемещения всех элементов с этим значением в их окончательное местоположение.^[1] Нравиться счетная сортировка, это эффективный вариант, если есть много повторяющихся значений. Действительно, сортировка выбора выполняет один проход по оставшимся элементам для каждого перемещенного элемента. Сортировка бинго выполняет один проход для каждого значения (не элемента): после первого прохода для поиска наибольшего значения следующие проходы могут перемещать каждый элемент с этим значением в его конечное местоположение, находя следующее значение, как показано ниже псевдокод (массивы отсчитываются от нуля, а цикл for включает как верхний, так и нижний пределы, как в Паскаль ):

бинго(множество А){Эта процедура сортируется в порядке возрастания. }начинать    Максимум := длина(А)-1;    {Первая итерация написана так, чтобы она выглядела очень похожей на последующие, но      без свопов. }    nextValue := А[Максимум];    за я := Максимум - 1 вниз 0 делать        если А[я] > nextValue тогда            nextValue := А[я];    пока (Максимум > 0) и (А[Максимум] = nextValue) делать        Максимум := Максимум - 1;    пока Максимум > 0 делать начинать        ценить := nextValue;        nextValue := А[Максимум];        за я := Максимум - 1 вниз 0 делать             если А[я] = ценить тогда начинать                 замена(А[я], А[Максимум]);                 Максимум := Максимум - 1;             конец еще если А[я] > nextValue тогда                 nextValue := А[я];        пока (Максимум > 0) и (А[Максимум] = nextValue) делать            Максимум := Максимум - 1;    конец;конец;

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

Смотрите также

• Алгоритм выбора

Рекомендации

внешняя ссылка

• Анимированные алгоритмы сортировки: сортировка по выделению на Wayback Machine (архивировано 7 марта 2015 г.) - графическая демонстрация