93
правки
Изменения
Нет описания правки
'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem). == Редактирование Задача сортировки =='''На входе''' последовательность из <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>. == Алгоритм == Шаг 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 отсортирован
