Изменения

Перейти к: навигация, поиск

Сортировка выбором

408 байт убрано, 22:21, 20 мая 2012
Нет описания правки
'''Сортировка выбором''' (англ. '''selection sort''') {{- это --}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{- --}} количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem). == Задача сортировки =='''На входе''' последовательность из <tex>n</tex> чисел.  '''На выходе''' отсортированная последовательность по неубыванию.
== Алгоритм ==
[[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]]
0. Назовем элементы массива списком.
1. Находим номер минимального элемента из текущего спискамассива.
2. Меняем минимальный элемент с первым элементом спискамассива.
3. Если список текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка текущего массива.
== Реализация ==
// Входной массив 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]);
93
правки

Навигация