Изменения

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

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

2== Псевдокод =='''Вариант 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])

3'''Вариант 2. Если текущий массив пуст'''Второй вариант немного более экономный. Здесь мы будем менять местами элементы только <tex>1</tex> раз для каждого <tex>i</tex>, то данный массив отсортированвсего будет нужно <tex>O(n)</tex> обменов. Иначе вернемся к шагу 1Для этого сначала мы будем проходить по всем еще не отсортированным элементам, искать минимальный, убрав и только потом менять местами минимальный и первый элемент из текущего массиванеотсортированных.

== Реализация == // Входной массив x, содержащий '''function''' selectionSort('''T[n элементов.]''' a): '''for ''' i = 0 '''to ''' n - 12 min = i; '''for ''' j = i + 1 '''to ''' n - 1 '''if x''' a[j] < xa[min] min = j; swap(xa[i], xa[min]); // Массив x отсортирован

Пусть дана последовательность из <tex>65</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>. Будем выделять текущий элемент на каждом шаге фиолетовым цветом, а минимальный черным жирным.

!style="background-color:#EEE"| До!style="background-color:#EEE"| ПослеМассив

|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2'''''текущий массив начинается с первого элемента)''

|style="background-color:#FFF;padding:2px 10px"| <span style="color:darkviolet">'''5 2''' </span> 4 3 1|<span style="background-color:#FFF;padding:2px 10pxblack"| >'''2 51''' 4 </span> 2 3 1|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй Находим первый минимальный элемент с первым и меняет их местами.{{---}} '''1'''

|colspanstyle=3"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"| Меняем минимальный и первый элементы местами

|stylecolspan="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1 |style="background-color:#FFF;padding:2px 10px"| 2 '''4 5'Второй проход (текущий массив начинается со следующего элемента)'' 3 1|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами

|style="background-color:#FFF;padding:2px 10px"| 1 <span style="color:darkviolet">'''2 4''' </span> 5 3 1|<span style="background-color:#FFF;padding:2px 10pxblack"| >'''2 4''' 5 </span> 3 1|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуетсяНаходим следующий минимальный элемент {{---}} '''2'''

|colspanstyle=3"background-color:#FFF;padding:2px 10px"|1 <span style="color:black">''Третий проход (проталкиваем четвертый — '2'''</span> 5 <span style="color:darkviolet">'3''4''')''</span> 3|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами

|stylecolspan="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5'Третий проход (текущий массив начинается со следующего элемента)'' 1|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами

|style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:darkviolet">'''4 35''' 5 1|</span> 4 <span style="background-color:#FFF;padding:2px 10pxblack"| 2 >'''3 4''' 5 1</span>|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местамиНаходим следующий минимальный элемент {{---}} '''3'''

|style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:black">'''2 3''' </span> 4 5 1|<span style="background-color:#FFF;padding:2px 10pxdarkviolet"| >'''2 35''' 4 5 1</span>|style="background-color:#FFF;padding:2px 10px"| Второй Меняем минимальный и первый отсортированы, swap не требуетсятретий элементы местами

|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1'''''текущий массив начинается со следующего элемента)''

|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 <span style="color:black">'''5 14'''|</span> <span style="background-color:#FFF;padding:2px 10pxblack"| 2 3 4 '''1 >5'''</span>|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый Находим следующий минимальный элемент {{---}} '''4'''. Меняем его местамис самим собой.

|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами|-|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5 |style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами|-|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.

== Ссылки Источники информации == *[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