Сортировка выбором — различия между версиями
Krotser (обсуждение | вклад) (→Алгоритм) |
Krotser (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | '''Сортировка выбором''' (англ. '''selection sort''') - | + | '''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Алгоритм == | == Алгоритм == | ||
[[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]] | [[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]] | ||
| − | |||
| − | 1. Находим номер минимального элемента из текущего | + | 1. Находим номер минимального элемента из текущего массива. |
| − | 2. Меняем минимальный элемент с первым элементом | + | 2. Меняем минимальный элемент с первым элементом массива. |
| − | 3. Если | + | 3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива. |
| Строка 25: | Строка 19: | ||
== Реализация == | == Реализация == | ||
// Входной массив x, содержащий n элементов. | // Входной массив x, содержащий n элементов. | ||
| − | for | + | for i = 0 to n - 1 |
| − | + | min = i; | |
| − | for | + | for j = i + 1 to n - 1 |
| − | if | + | if x[j] < x[min] |
min = j; | min = j; | ||
swap(x[i], x[min]); | swap(x[i], x[min]); | ||
Версия 22:21, 20 мая 2012
Сортировка выбором (англ. selection sort) — простой алгоритм сортировки со сложностью , где — количество элементов для сортировки.
Содержание
Алгоритм
1. Находим номер минимального элемента из текущего массива.
2. Меняем минимальный элемент с первым элементом массива.
3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.
Пример
Пусть дана последовательность из элементов .
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.
Реализация
// Входной массив x, содержащий n элементов.
for i = 0 to n - 1
min = i;
for j = i + 1 to n - 1
if x[j] < x[min]
min = j;
swap(x[i], x[min]);
// Массив x отсортирован
Ссылки
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
