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

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

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

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

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

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

Пример

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

Сортированный подсписок	Несортированный подсписок	Наименьший элемент в несортированном списке
()	(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// Find the minimum element in arr[0...4]// and place it at beginning11 25 12 22 64// Find the minimum element in arr[1...4]// and place it at beginning of arr[1...4]11 12 25 22 64// Find the minimum element in arr[2...4]// and place it at beginning of arr[2...4]11 12 22 25 64// Find the minimum element in arr[3...4]// and place it at beginning of arr[3...4]11 12 22 25 64 

Реализации

Ниже приведена реализация C. на

/* a[0] to a[aLength-1] is the array to sort */int i,j;int aLength; // initialise to a's length/* advance the position through the entire array *//*   (could do i < aLength-1 because single element is also min element) */for (i = 0; i < aLength-1; i++){    /* find the min element in the unsorted a[i .. aLength-1] */    /* assume the min is the first element */    int jMin = i;    /* test against elements after i to find the smallest */    for (j = i+1; j < aLength; j++)    {        /* if this element is less, then it is the new minimum */        if (a[j] < a[jMin])        {            /* found new minimum; remember its index */            jMin = j;        }    }    if (jMin != i)     {        swap(&a[i], &a[jMin]);    }}

Сложность

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

$(n-1)+(n-2)+\dots +1=\sum _{i=1}^{n-1}i$

По арифметической прогрессии ,

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

что представляет собой сложность $O(n^{2})$ по количеству сравнений.

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

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

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

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

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

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

Варианты

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

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

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

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

bingo(array A){ This procedure sorts in ascending order by  repeatedly moving maximal items to the end. }begin    last := length(A) - 1;    { The first iteration is written to look very similar to the subsequent ones,      but without swaps. }    nextMax := A[last];    for i := last - 1 downto 0 do        if A[i] > nextMax then            nextMax := A[i];    while (last > 0) and (A[last] = nextMax) do        last := last - 1;    while last > 0 do begin        prevMax := nextMax;        nextMax := A[last];        for i := last - 1 downto 0 do             if A[i] > nextMax then                 if A[i] <> prevMax then                     nextMax := A[i];                 else begin                     swap(A[i], A[last]);                     last := last - 1;                 end        while (last > 0) and (A[last] = nextMax) do            last := last - 1;    end;end;

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

См. также

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

Ссылки

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