Изменения

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

== Задача сортировки Алгоритм =='''На входе''' последовательность из каждом <tex>ni</tex> чисел-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив, отсортированный по неубыванию.

== Псевдокод =='''На выходеВариант 1.''' отсортированная последовательность Будем каждый раз проходить по возрастаниювсем еще не отсортированным элементам, и, как только найдем элемент меньше, чем первый из неотсортированных, поменяем их местами.Таким образом будет нужно <tex>O(n^2)</tex> обменов (для каждого <tex>i</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])

'''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>. Новый массив начинается со следующего элемента, так как все предыдущие элементы уже отсортированы. Перейти к шагу 1Будем выделять текущий элемент на каждом шаге фиолетовым цветом, если массив не пустойа минимальный черным жирным.

{| 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'''</ Входной массив x, содержащий n элементов.span> 2 3|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' |- for (i |style= 0 to n "background- color:#FFF;padding:2px 10px"| <span style="color:black">'''1)'''</span> 4 <span style="color:darkviolet">'''5'''</span> 2 3 int min |style= i"background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами for |-|colspan=3|''Второй проход (j текущий массив начинается со следующего элемента)''|-|style= i + "background-color:#FFF;padding:2px 10px"| 1 to n <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''' |- if (x[j] |style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:black">'''3'''</span> 4 <span style="color:darkviolet">'''5'''< x[min])/span> min |style= j"background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами swap|-|colspan=3|''Четвертый проход (x[i], x[min]текущий массив начинается со следующего элемента)''|-|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"| Массив x отсортирован|}

== Ссылки См. также == *[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 [Сортировка пузырьком]]* [[Сортировка вставками]]* [[Сортировка кучей]]* [[Сортировка слиянием]]* [[Быстрая сортировка]]* [[Сортировка подсчетом]]* [[Сортировка выбором в русской википедииШелла]]

== Литература Источники информации ==*[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 Википедия {{---}} Сортировка выбором]