Сортировка выбором

Алгоритм сортировки

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

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

Эффективность сортировки выбором по времени квадратична, поэтому существует ряд методов сортировки, которые имеют лучшую временную сложность, чем сортировка выбором.

Пример

Вот пример этого алгоритма сортировки, сортирующего пять элементов:

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

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

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

обр[] = 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.

/* от a[0] до a[aLength-1] — это массив для сортировки */интервал я , j ; int Длина ; // инициализируем длину a  /* продвигаем позицию по всему массиву *//* (можно сделать i < aLength-1, потому что отдельный элемент также является минимальным элементом) */для ( я = 0 ; я < aLength -1 ; я ++ )       { /* найти минимальный элемент в неотсортированном a[i .. aLength-1] */ /* предположим, что min — это первый элемент */ интервал jMin = я ;    /* проверка элементов после i, чтобы найти наименьший */ для ( j = я + 1 ; j < aLength ; j ++ )        { /* если этот элемент меньше, то это новый минимум */ если ( а [ j ] < а [ jMin ])    { /* найден новый минимум; запомнить его индекс */ jМин = j ;   продолжать ; } } если ( jMin != я )     { поменять местами ( a [ i ], a [ jMin ]);  }}

Сложность

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

${\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})}$

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

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

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

Хотя сортировка выбором предпочтительнее сортировки вставкой с точки зрения количества операций записи ( подкачки вместо свопов, где каждая замена представляет собой две записи), это примерно в два раза превышает теоретический минимум, достигаемый при циклической сортировке , которая выполняет не более n операций записи. Это может быть важно, если запись значительно дороже, чем чтение, например, в EEPROM или флэш-памяти , где каждая запись сокращает срок службы памяти. ${\displaystyle n-1}$ ${\displaystyle n(n-1)/2}$

Сортировка выбором может быть реализована без непредсказуемых ветвей в интересах предсказателей ветвей ЦП путем нахождения местоположения минимума с помощью кода без ветвей и последующего безусловного выполнения замены.

Наконец, сортировка выбором значительно проигрывает на больших массивах алгоритмам «разделяй и властвуй», таким как сортировка слиянием . Однако сортировка вставкой и сортировка выбором обычно выполняются быстрее для небольших массивов (т. е. менее 10–20 элементов). На практике полезной оптимизацией рекурсивных алгоритмов является переключение на сортировку вставкой или сортировку выбором для «достаточно маленьких» подсписков. ${\displaystyle \Theta (n\log n)}$

Варианты

Пирамидальная сортировка значительно улучшает базовый алгоритм за счет использования неявной структуры данных кучи для ускорения поиска и удаления самых нижних данных. При правильной реализации куча позволит найти следующий наименьший элемент по времени вместо внутреннего цикла при обычной сортировке выбором, сокращая общее время работы до . ${\displaystyle \Theta (\log n)}$ ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (n\log n)}$

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

Сортировка выбором может быть реализована как стабильная сортировка , если вместо замены на шаге 2 минимальное значение вставляется в первую позицию, а промежуточные значения сдвигаются вверх. Однако эта модификация либо требует структуры данных, которая поддерживает эффективные вставки или удаления, например связанный список, либо приводит к выполнению записи. ${\displaystyle \Theta (n^{2})}$

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

бинго ( массив A ) { Эта процедура сортирует по возрастанию,  многократно перемещая максимальное количество элементов в конец. } начало последним := длина ( A ) - 1 ;      { Первая итерация написана так, чтобы выглядеть очень похожей на последующие,  но без свопов. } nextMax := A [ последний ] ; for i := Last - 1 до 0 do if A [ i ] > nextMax then nextMax := A [ i ] ; while ( last > 0 ) и ( A [ last ] = nextMax ) dolast : = last - 1 ;                                   while Last > 0 do Begin prevMax := nextMax ; nextMax := A [ последний ] ; for i := last - 1 вплоть до 0 do if A [ i ] > nextMax then if A [ i ] <> prevMax then nextMax := A [ i ] ; иначе начать замену ( A [ i ] , A [ last ]) ; последний := последний - 1 ; end while ( last > 0 ) и ( A [ last ] = nextMax ) do Last := Last - 1 ; конец ; конец ;                                                          

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

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

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

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

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

• Дональд Кнут . Искусство компьютерного программирования , Том 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 г.) - графическая демонстрация