Сортировка выбором — различия между версиями
Krotser (обсуждение | вклад) (→Алгоритм) |
Krotser (обсуждение | вклад) (→Задача сортировки) |
||
| Строка 4: | Строка 4: | ||
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). | '''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). | ||
| − | '''На выходе''' | + | '''На выходе''' отсортированная последовательность (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>. |
== Алгоритм == | == Алгоритм == | ||
Версия 13:46, 20 мая 2012
Сортировка выбором (англ. selection sort) - это простой алгоритм сортировки со сложностью , где - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).
Задача сортировки
На входе последовательность из чисел ().
На выходе отсортированная последовательность () таким образом, что для ее членов выполняется .
Алгоритм
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]);
// Массив x отсортирован
Ссылки
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
