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

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

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	О (п^2) сравнения, (п) свопы
Лучший случай спектакль	О (п^2) сравнения, O (1) свопы
Средний спектакль	О (п^2) сравнения, (п) свопы
Худший случай космическая сложность	O (1) вспомогательный

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

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

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

Пример

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

Отсортированный подсписок	Несортированный подсписок	Наименьший элемент в несортированном списке
()	(11, 25, 12, 22, 64)	11
(11)	(25, 12, 22, 64)	12
(11, 12)	(25, 22, 64)	22
(11, 12, 22)	(25, 64)	25
(11, 12, 22, 25)	(64)	64
(11, 12, 22, 25, 64)	()

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

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

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

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 (n-1)+(n-2)+...+1=sum _{i=1}^{n-1}i}$

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

${displaystyle sum _{i=1}^{n-1}i={frac {(n-1)+1}{2}}(n-1)={frac {1}{2}}n(n-1)={frac {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;    конец;конец;

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

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

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

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

1. Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. «Сортировка бинго». Словарь алгоритмов и структур данных.

• Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Третье издание. Аддисон – Уэсли, 1997. ISBN  0-201-89685-0. Страницы 138–141 раздела 5.2.3: Сортировка по выделению.
• Ананий Левитин. Введение в разработку и анализ алгоритмов, 2-е издание. ISBN  0-321-35828-7. Раздел 3.1: Сортировка выбора, стр. 98–100.
• Роберт Седжвик. Алгоритмы в C ++, части 1–4: основы, структура данных, сортировка, поиск: основы, структуры данных, сортировка, поиск точек. 1–4, Второе издание. Аддисон – Уэсли Лонгман, 1998. ISBN  0-201-35088-2. Страницы 273–274

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

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