Просмотр кода страницы Сортировка выбором

{{Алгоритм
| предназначение = [[Алгоритм сортировки]]|изображение
| подпись = Действие алгоритма на примере сортировки случайных точек.
| данные = [[Массив (программирование)|Массив]]
| время = <math>O(n^2)</math>
| лучшее-время = <math>O(n^2)</math>
| среднее-время = <math>O(n^2)</math>
| память = <math>O(1)</math>
}}
'''Сортировка выбором''' ([[Английский язык|англ.]] ''selection sort'') — [[алгоритм сортировки]]. Может быть как устойчивый, так и неустойчивый.
На массиве из <math>n</math> элементов имеет время выполнения в худшем, среднем и лучшем случае <math>O(n^2)</math>, предполагая что сравнения делаются за постоянное время.

== Алгоритм без дополнительного выделения памяти ==
[[Файл:Selection-Sort-Animation.gif|thumb|288px|Сортировка выбором]]
Шаги алгоритма:
# Находим номер минимального значения в текущем списке.
# Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
# Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

== Реализация алгоритма на языках программирования ==
Далее находится пример [[Устойчивая сортировка|неустойчивой]] реализации данного алгоритма:

=== [[C++]] ===
<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>

=== [[C Sharp|C#]] ===

<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>

=== [[PL/SQL]] ===

<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>
=== [[Java]] ===

<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>

=== [[Ruby]] ===
<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>
=== [[Swift (язык программирования)|Swift]] ===
<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>
=== [[PascalABC.NET]] ===
<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>

=== [[Python]] ===
<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>

=== [[Go]] ===
<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>

=== [[Rust (язык программирования)|Rust]] ===
<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>

=== Почему такая реализация неустойчива? ===
Покажем, почему данная реализация является неустойчивой.

Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.<br>
Массив до сортировки: <code>{ (2, a), (2, b), (1, a) }</code><br>
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность: <code>{ (1, a), (2, b), (2, a) }</code>

Теперь заметим, что взаимное расположение элементов <code>(2, a)</code> и <code>(2, b)</code> изменилось.<br>
Таким образом, <u>рассматриваемая реализация является неустойчивой</u>.

== Сравнение с другими алгоритмами сортировки ==
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно <math>n-1</math>, что в <math>n/2</math> раз меньше, чем в [[Сортировка пузырьком|сортировке пузырьком]].<br>
Число проходов по внутреннему циклу равно <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 секунд.<br>
[[Пирамидальная сортировка]] сильно улучшает базовый алгоритм, используя структуру данных «[[Сортирующее дерево|куча]]» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

== Литература ==
* {{source|Q21694522|part=Глава 3. Метод грубой силы: Сортировка выбором|pages=143—144}}
* {{книга
|часть = '''Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором'''
|заглавие = Алгоритмы на C++
|оригинал = Algorithms in C++
|автор = Роберт Седжвик
|ссылка = 
|isbn = 978-5-8459-1650-1
|страницы = 246-247
|год = 2011
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}
* {{Книга:CLRS}}

== См. также ==
* [[Алгоритм сортировки#Список алгоритмов сортировки|Список алгоритмов сортировки]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]

== Ссылки ==
* {{cite web|url=http://algolist.manual.ru/sort/select_sort.php|title=Статья "Сортировка выбором" на сайте algolist.manual.ru|accessdate=2012-09-25}} 
* [https://airtucha.github.io/SortVis/ Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом] 

{{wikibooks|Примеры реализации сортировки выбором|Примеры реализации сортировки выбором}}

{{Алгоритмы сортировки}}
[[Категория:Алгоритмы сортировки]]