Сортировка выбором
Шаблон:Алгоритм Сортировка выбором (англ. selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из <math>n</math> элементов имеет время выполнения в худшем, среднем и лучшем случае <math>O(n^2)</math>, предполагая что сравнения делаются за постоянное время.
Алгоритм без дополнительного выделения памяти
Шаги алгоритма:
- Находим номер минимального значения в текущем списке.
- Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
- Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.
Реализация алгоритма на языках программирования
Далее находится пример неустойчивой реализации данного алгоритма:
<source lang="cpp" line="1"> template <typename type_arr> void selection_sort(type_arr *arr, int size) {
for (int i = 0; i < size - 1; i++)
{
int min_index = i;
for (int j = i + 1; j < size; j++)
{
if (arr[j] < arr[min_index])
{
min_index = j;
}
}
if (min_index != i)
{
swap(arr[i], arr[min_index]);
}
}
} </source>
<source lang="csharp" line="1"> public static IList<T> Selection<T>(IList<T> list) where T : IComparable<T> {
for (int i = 0; i < list.Count - 1; ++i)
{
int min = i;
for (int j = i + 1; j < list.Count; ++j)
{
if (list[j].CompareTo(list[min]) < 0)
{
min = j;
}
}
var dummy = list[i];
list[i] = list[min];
list[min] = dummy;
}
return list;
} </source>
<source lang="plsql" line="1"> type sort_choice_list is table of integer index by binary_integer;
function SORT_CHOICE return sort_choice_list
IS
list sort_choise_list;
l_min pls_integer;
l_dummy pls_integer;
begin
for n in 1..100 loop
list(n):=dbms_random.random; --инициализация массива случайными числами
end loop;
for i in list.first..list.last loop
l_min:=i;
for j in (i + 1)..list.last loop
if (list(j) < list(l_min)) then
l_min := j;
end if;
end loop;
l_dummy:=list(i);
list(i):=list(l_min);
list(l_min) := l_dummy;
end loop;
return list;
end SORT_CHOICE; </source>
<source lang="java" line="1"> public static void selectionSort(int [] arr) { int n = arr.length; for(int i = 0; i<n-1; i++) { int minIndex = i; for(int j=i+1; j<n; j++) { if(arr[j]<arr[minIndex]) { minIndex = j; } } if(minIndex!=i) swap(arr,i,minIndex);
} }
</source>
<syntaxhighlight lang="ruby" line="1" start="1"> def selection_sort(array) for min in 0..array.count-2 least = min for j in (min + 1)..array.count-1 if array[j] < array[least] least = j end end temp = array[min] array[min] = array[least] array[least] = temp end end </syntaxhighlight>
<syntaxhighlight lang="swift" line="1" start="1"> func selectionSort<Element>(_ array: inout Array<Element>) where Element: Comparable { for min in 0..<array.count - 1 { for j in min..<array.count { if array[j] < array[min] { let temp = array[min] array[min] = array[j] array[j] = temp } } } } </syntaxhighlight>
<syntaxhighlight lang=pascal line="1"> begin
var a := ArrRandom; a.Println;
for var i:=0 to a.High do
Swap(a[i],a[i+a[i:].IndexMin]);
a.Println;
end </syntaxhighlight>
<source lang="python" line="1"> def select_sort(A):
for i in range(len(A) - 1):
min_index = i
for k in range(i + 1, len(A)):
if A[k] < A[min_index]:
A[k], A[min_index] = A[min_index], A[k]
return A
</source>
<syntaxhighlight lang="go" line="1"> func selectionSort(nums []int) {
n := len(nums)
for i := 0; i < n; i++ {
min := i
for j := i + 1; j < n; j++ {
if nums[j] < nums[min] {
min = j
}
}
nums[i], nums[min] = nums[min], nums[i]
}
} </syntaxhighlight>
<syntaxhighlight lang="rust" line="1"> fn selection_sort<T: Ord>(array: &mut [T]) {
let n = array.len();
for i in 0..n {
let mut min_index = i;
for j in i + 1..n {
if array[min_index] > array[j] {
min_index = j;
}
}
if min_index != i {
array.swap(i, min_index);
}
}
} </syntaxhighlight>
Почему такая реализация неустойчива?
Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки: { (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность: { (1, a), (2, b), (2, a) }
Теперь заметим, что взаимное расположение элементов (2, a) и (2, b) изменилось.
Таким образом, рассматриваемая реализация является неустойчивой.
Сравнение с другими алгоритмами сортировки
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно <math>n-1</math>, что в <math>n/2</math> раз меньше, чем в сортировке пузырьком.
Число проходов по внутреннему циклу равно <math>n-1</math> даже в случае сортировки частично или полностью отсортированного массива.
- Число сравнений в теле цикла равно <math>(n-1)*n/2</math>.
- Число сравнений в заголовках циклов <math>(n-1)*n/2</math>.
- Число сравнений перед операцией обмена <math>n-1</math>.
- Суммарное число сравнений <math>n^2-1</math>.
- Число обменов <math>n-1</math>.
Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈ 40 секунд, а ещё более улучшенной сортировкой пузырьком ≈ 30 секунд.
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.