65
правок
Изменения
м
== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
Исправлена ошибка в таблице и доработано выделение цветом.
'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
== Алгоритм ==
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив , отсортированный по неубыванию.
== Реализация Псевдокод =='''Вариант 1.'''Будем каждый раз проходить по всем еще не отсортированным элементам, и, как только найдем элемент меньше, чем первый из неотсортированных, поменяем их местами. Таким образом будет нужно <tex>O(n^2)</tex> обменов (для каждого <tex>i</tex> требуется <tex>O(n-i)</tex> обменов). SelectionSort'''function''' selectionSort('''T[n]''' a): '''for ''' i = 0 '''to ''' n - 1 min = i;2 '''for ''' j = i + 1 '''to ''' n- 1 '''if ''' a[ji] < > a[minj] min = j; swap(a[i], a[minj]);
'''Вариант 2.''' SelectionSortВторой вариант немного более экономный. Здесь мы будем менять местами элементы только <tex>1</tex> раз для каждого <tex>i</tex>, всего будет нужно <tex>O(n)</tex> обменов. Для этого сначала мы будем проходить по всем еще не отсортированным элементам, искать минимальный, и только потом менять местами минимальный и первый из неотсортированных. '''function''' selectionSort('''T[n]''' a): '''for ''' i = 0 '''to ''' n - 12 min = i '''for ''' j = i + 1 '''to ''' n- 1 '''if ''' a[ij] > < a[jmin] min = j swap(a[i], a[jmin]);
== Пример ==
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>. Будем выделять текущий элемент на каждом шаге фиолетовым цветом, а минимальный черным жирным.
{| style="background-color:#CCC;margin:0.5px"
|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 4 <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''' 4 </span> 5 <span style="color:darkviolet">'''54''' </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 5 <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''' 5 </span> 4 <span style="color:darkviolet">'''45'''</span>
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 <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"| . Меняем минимальный и четвертый элементы его местамис самим собой.
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|}
== См. также ==
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]
* [[Сортировка Шелла]]
== Ссылки Источники информации == *[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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
