65
правок
Изменения
Тикет 8.1
'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
== Алгоритм ==
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.
== Реализация Псевдокод =='''Вариант 1.'''Будем каждый раз проходить по всем еще не отсортированным элементам, и, как только найдем элемент меньше, чем первый из неотсортированных, поменяем их местами. Таким образом для каждого <tex>i</tex> нужно <tex>O(n-i)</tex> обменов. '''function''' SelectionSort(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>. Для этого сначала мы будем проходить по всем еще не отсортированным элементам, искать минимальный, и только потом менять местами минимальный и первый из неотсортированных. '''function''' SelectionSort(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]);
== Пример ==
|}
== См. также ==
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]
* [[Сортировка Шелла]]
== Ссылки Источники информации == *[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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
