В информатике , выбор рода является в месте сравнение алгоритм сортировки . Его временная сложность составляет O ( n 2 ) , что делает его неэффективным для больших списков и, как правило, хуже, чем аналогичная сортировка вставкой . Сортировка по выбору отличается своей простотой и имеет преимущества в производительности по сравнению с более сложными алгоритмами в определенных ситуациях, особенно когда вспомогательная память ограничена.
Класс | Алгоритм сортировки |
---|---|
Структура данных | Множество |
Наихудшая производительность | О ( n 2 ) сравнений, О ( n ) свопов |
Лучшая производительность | О ( n 2 ) сравнений, O ( 1 ) свопов |
Средняя производительность | О ( n 2 ) сравнений, О ( n ) свопов |
Сложность пространства в наихудшем случае | O (1) вспомогательный |
Алгоритм делит входной список на две части: отсортированный подсписок элементов, который создается слева направо в начале (слева) списка, и подсписок оставшихся несортированных элементов, занимающих остальную часть списка. Первоначально отсортированный подсписок пуст, а несортированный подсписок представляет собой весь входной список. Алгоритм выполняется путем нахождения наименьшего (или наибольшего, в зависимости от порядка сортировки) элемента в несортированном подсписке, обмена (перестановки) его с крайним левым несортированным элементом (помещая его в отсортированном порядке) и перемещения границ подсписка на один элемент вправо. .
Временная эффективность сортировки с выбором является квадратичной, поэтому существует ряд методов сортировки, которые имеют лучшую временную сложность, чем сортировка с выбором. Одна вещь, которая отличает сортировку выбора от других алгоритмов сортировки, заключается в том, что она делает минимально возможное количество перестановок, n - 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 . Дополнительные реализации можно найти на странице обсуждения этой статьи в Википедии .
/ * от [0] до [aLength-1] - это массив для сортировки * /int i , j ;int aLength ; // инициализируем длину a/ * продвигаем позицию по всему массиву * // * (можно сделать i ,>для ( я = 0 ; я < aLength -1 ; я ++ ){ / * находим элемент min в несортированном a [i .. aLength-1] * / / * предполагаем, что min является первым элементом * / int jMin = я ; / * тестируем элементы после i, чтобы найти наименьший * / для ( j = i + 1 ; j < aLength ; j ++ ) { / * если этот элемент меньше, то это новый минимум * / если ( a [ j ] < a [ jMin ]) { / * найден новый минимум; запомнить его индекс * / jMin = j ; } } если ( jMin ! = i ) { swap ( a [ i ], a [ jMin ]); }}
Сложность
Сортировку выбора нетрудно анализировать по сравнению с другими алгоритмами сортировки, поскольку ни один из циклов не зависит от данных в массиве. Для выбора минимума требуется сканирование элементы (принимая сравнения), а затем переставив его в первую позицию. Чтобы найти следующий самый низкий элемент, необходимо просканировать оставшиесяэлементы и так далее. Следовательно, общее количество сравнений равно
По арифметической прогрессии ,
что является сложным по количеству сравнений. Для каждого из этих сканирований требуется одна замена для элементы (последний элемент уже на месте).
Сравнение с другими алгоритмами сортировки
Среди алгоритмов квадратичной сортировки (алгоритмы сортировки с простым средним случаем ( n 2 ) ) сортировка по выбору почти всегда превосходит пузырьковую сортировку и сортировку гномов . Сортировка вставкой очень похожа на то, что после k- й итерации перваяэлементы в массиве отсортированы. Преимущество сортировки вставкой состоит в том, что она сканирует ровно столько элементов, сколько необходимо для размещенияst элемент, в то время как сортировка выбора должна сканировать все оставшиеся элементы, чтобы найти st элемент.
Простой расчет показывает, что сортировка вставкой обычно выполняет примерно вдвое меньше сравнений, чем сортировка по выбору, хотя она может выполнять столько же или гораздо меньше в зависимости от порядка, в котором находился массив до сортировки. Для некоторых приложений реального времени преимуществом является то, что сортировка выбора будет выполняться одинаково независимо от порядка в массиве, в то время как время выполнения сортировки вставкой может значительно различаться. Однако чаще это дает преимущество сортировки вставкой, поскольку она работает намного эффективнее, если массив уже отсортирован или «почти отсортирован».
Хотя сортировка выбора предпочтительнее сортировки вставкой с точки зрения количества записей ( свопы против до swap, при этом каждый swap равен двум операциям записи), это примерно вдвое больше теоретического минимума, достигаемого циклической сортировкой , которая выполняет не более n операций записи. Это может быть важно, если запись значительно дороже чтения, например, с EEPROM или флэш-памятью , где каждая запись сокращает срок службы памяти.
Сортировка выбора может быть реализована без непредсказуемых ветвлений в пользу предсказателей ветвления ЦП , путем нахождения местоположения минимума с помощью кода без ветвлений и последующего выполнения замены без каких-либо условий.
Наконец, сортировка по выбору значительно превосходит большие массивы на алгоритмы разделяй и властвуй, такие как сортировка слиянием . Однако сортировка вставкой или сортировка по выбору обычно быстрее для небольших массивов (т.е. менее 10–20 элементов). На практике полезной оптимизацией рекурсивных алгоритмов является переключение на сортировку вставкой или сортировку по выбору для «достаточно маленьких» подсписок.
Варианты
Heapsort значительно улучшает базовый алгоритм за счет использования неявной структуры данных кучи для ускорения поиска и удаления самых низких данных. При правильной реализации куча позволит найти следующий нижний элемент в время вместо для внутреннего цикла при нормальной сортировке выбора, сокращая общее время работы до .
Двунаправленный вариант сортировки с выбором (называемый сортировкой с двойным выбором или иногда с сортировкой по коктейлю из-за его сходства с сортировкой с помощью шейкер ) находит как минимальные, так и максимальные значения в списке на каждом проходе. Для этого требуется три сравнения на два элемента (сравнивается пара элементов, затем больший сравнивается с максимумом, а меньший - с минимумом), а не одно сравнение обычной сортировки выбора для каждого элемента, но требует лишь вдвое меньшего количества проходов, чистая экономия 25%.
Сортировка выбора может быть реализована как стабильная сортировка, если вместо замены на шаге 2 минимальное значение вставлено в первую позицию, а промежуточные значения сдвинуты вверх. Однако для этой модификации либо требуется структура данных, поддерживающая эффективные вставки или удаления, например связанный список, либо она приводит к выполнению пишет.
В варианте сортировки бинго элементы сортируются путем многократного просмотра оставшихся элементов, чтобы найти наибольшее значение, и перемещения всех элементов с этим значением в их окончательное местоположение. [1] Подобно сортировке с подсчетом , это эффективный вариант, если имеется много повторяющихся значений: сортировка выбора выполняет один проход по оставшимся элементам для каждого перемещенного элемента , а сортировка Бинго выполняет один проход для каждого значения . После начального прохода для поиска наибольшего значения последующие проходы перемещают каждый элемент с этим значением в его окончательное местоположение, находя следующее значение, как в следующем псевдокоде (массивы отсчитываются от нуля, а цикл for включает как верхний, так и нижний пределы , как в Паскале ):
бинго ( массив A ){Эта процедура сортирует в порядке возрастания, многократно перемещая максимальное количество элементов в конец. } начало последним : = длина ( A ) - 1 ; {Первая итерация написана так, чтобы она выглядела очень похожей на последующие, но без перестановок. } nextMax : = A [ последний ] ; for i : = last - 1 до 0 делать, если A [ i ] > nextMax, then nextMax : = A [ i ] ; while ( last > 0 ) и ( A [ last ] = nextMax ) do last : = last - 1 ; в то время как в прошлом > 0 делать начинают prevMax : = nextMax ; nextMax : = A [ последний ] ; for i : = last - 1 до 0 делать, если A [ i ] > nextMax, тогда если A [ i ] <> prevMax, то nextMax : = A [ i ] ; иначе начать обмен ( A [ i ] , A [ last ]) ; last : = last - 1 ; конец while ( last > 0 ) и ( A [ last ] = nextMax ) do last : = last - 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
Внешние ссылки
- Анимированные алгоритмы сортировки: сортировка выбора на обратном пути (архивировано 7 марта 2015 г.) - графическая демонстрация