Изменения

'''Сортировка выбором''' (англ. '''selection sort''') {{- это --}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{--- }} количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).

== Задача сортировки Алгоритм ==На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив, отсортированный по неубыванию. == Псевдокод =='''На входеВариант 1.''' последовательность Будем каждый раз проходить по всем еще не отсортированным элементам, и, как только найдем элемент меньше, чем первый из неотсортированных, поменяем их местами. Таким образом будет нужно <tex>O(n^2)</tex> чисел обменов (для каждого <tex>x_1, x_2i</tex> требуется <tex>O(n-i)</tex> обменов). '''function''' selectionSort('''T[n]''' a): '''for''' i = 0 '''to''' n - 2 '''for''' j = i + 1 '''to''' n - 1 '''if''' a[i] > a[j] swap(a[i], a[j]) '''Вариант 2.'''Второй вариант немного более экономный..Здесь мы будем менять местами элементы только <tex>1</tex> раз для каждого <tex>i</tex>, x_nвсего будет нужно <tex>O(n)</tex>обменов. Для этого сначала мы будем проходить по всем еще не отсортированным элементам, искать минимальный, и только потом менять местами минимальный и первый из неотсортированных.  '''function''' selectionSort('''T[n]''' a): '''for''' i = 0 '''to''' n - 2 min = i '''for''' j = i + 1 '''to''' n - 1 '''if''' a[j] < a[min] min = j swap(a[i], a[min]).

Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>. Будем выделять текущий элемент на каждом шаге фиолетовым цветом, а минимальный черным жирным. {| style="background-color:#CCC;margin:0.5px"!style= Алгоритм "background-color:#EEE"| Массив!style="background-color:#EEE"| Описание шага|-|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''|-|style="background-color:#FFF;padding:2px 10px"| <span style="color:darkviolet">'''5'''</span> 4 <span style="color:black">'''1'''</span> 2 3|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' |-|style="background-color:#FFF;padding:2px 10px"| <span style="color:black">'''1'''</span> 4 <span style="color:darkviolet">'''5'''</span> 2 3|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами|-|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''|-|style="background-color:#FFF;padding:2px 10px"| 1 <span style="color:darkviolet">'''4'''</span> 5 <span style="color:black">'''2'''</span> 3|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' |-|style="background-color:#FFF;padding:2px 10px"| 1 <span style="color:black">'''2'''</span> 5 <span style="color:darkviolet">'''4'''</span> 3|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами|-|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''|-|style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:darkviolet">'''5'''</span> 4 <span style="color:black">'''3'''</span>|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' |-|style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:black">'''3'''</span> 4 <span style="color:darkviolet">'''5'''</span>|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами|-|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''|-|style="background-color:#FFF;padding:2px 10px"| 1 2 3 <span style="color:black">'''4'''</span> <span style="color:black">5</span>|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4'''. Меняем его местами с самим собой.|-|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован|}

Шаг 1. Выбираем минимальный элемент из текущего массива== См.также ==* [[Сортировка пузырьком]]* [[Сортировка вставками]]* [[Сортировка кучей]]* [[Сортировка слиянием]]* [[Быстрая сортировка]]* [[Сортировка подсчетом]]* [[Сортировка Шелла]]

Шаг == Источники информации == *[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Википедия {{---}} Сортировка выбором]*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М. Ставим его на первое место: Издательский дом "Вильямс", 2005.ISBN 5-8459-0857-4

== Реализация ==[[Категория: Дискретная математика и алгоритмы]] // Входной массив x, содержащий n элементов. for (i = 0 to n - 1) int min = i; for (j = i + 1 to n - 1) if (x[j[Категория: Сортировки] < x[min]) min = j; swap(x[i[Категория: Квадратичные сортировки], x[min]); // Массив x отсортирован