Как сделать сортировку выбором
Обновлено: 07.07.2024
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.
На i-м шаге выбираем наименьший из элементов a[i] . a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.
Вне зависимости от номера текущего шага i, последовательность a[0]. a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
Для нахождения наименьшего элемента из n+1 рассматримаемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + . + 1 = 1/2 * ( n 2 +n ) = Theta(n 2 ).
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.
Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Устойчив ли этот метод ? Прежде, чем читать далее, попробуйте получить ответ самостоятельно.
Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них.
Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, так что метод неустойчив.
Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Алгоритм сортировки методом выбора начинается со сравнения первых двух элементов массива и их замены в случае необходимости. Например, если вы хотите отсортировать элементы массива в порядке возрастания и если первый элемент больше второго, вам нужно поменять местами элементы. Но, если первый элемент меньше второго, элементы остаются в своей последовательности. Затем снова первый элемент и третий элемент сравниваются и меняются местами, если это необходимо. Этот процесс продолжается до тех пор, пока не будет сравнен первый и последний элемент массива. Это завершает первый шаг выбора сортировки.
Если нужно отсортировать n элементов, процесс, упомянутый выше, следует повторить n-1 раз, чтобы получить требуемый результат. Для повышения производительности на втором шаге сравнение начинается со второго элемента, потому что после первого шага требуемое число автоматически помещается в первый. Аналогично, на третьем этапе сравнение начинается с третьего элемента и так далее. В случае сортировки в порядке возрастания, наименьший элемент будет первым, а в случае сортировки по убыванию, наибольший элемент будет первым.
Рассмотрим на рисунке работу алгоритма сортировки методом выбора.
Программа на C для сортировки элементов с использованием алгоритма сортировки методом выбора
Примечание: хотя эта программа написана на C, алгоритм сортировки выбора можно аналогичным образом использовать и на другом языке программирования.
Алгоритм сортировки выбора прост в использовании, но есть и другие алгоритмы сортировки, которые работает лучше, чем сортировка выбора. В частности, сортировка выбора не должна использоваться для сортировки большого количества элементов, если производительность имеет значение в этой программе.
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Сортировка выбором (Selection sort) — Алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ$$(n^2)$$, предполагая что сравнения делаются за постоянное время.
Алгоритм:
1) Ищем порядковый номер минимального значения в не отсортированной части массива.
2) Меняем его с крайним не отсортированным значением, если крайнее но отсортированное значение является минимальным ничего не делаем.
3) Повторяем пункты 1 и 2 пока весь массив не отсортируется.
Посмотрим алгоритм на примере:
Отсортируем массив: 524613 где каждая цифра это элемент массива.
Начало цикла, в массиве 524613 нет отсортированных чисел:
524613 -> |124653
2) 2 оказалась самым крайним не отсортированным значением, не меняем его положения
1|24653 -> 1|24653
3) Далее минимальным значением является 3, меняем её с 4.
12|4653-> 12|3654
3) Далее минимальным значением является 4, меняем её с 6.
123|654 -> 123|456
4) 5 оказалась самым крайним не отсортированным значением, не меняем его положения
123456 -> 1234|56
5) 6 оказалась самым крайним не отсортированным значением, не меняем его положения
Похожим методом является сортировка выбором (минимума или максимума).
Чтобы отсортировать массив, $n$ раз выберем минимум среди еще неотсортированных чисел и поставим его на свое место (а именно, на $k$-тую позицию после $k$-той итерации). Чтобы упростить реализацию, на $k$-ой итерации будем искать минимум на отрезке $[k, n - 1]$, меняя его местами с текущим $k$-тым элементом, после чего отрезок $[0, k]$ будет отсортирован.
Доказательства корректности и времени работы аналогичны пузырьковой сортировке: после каждой из $O(n)$ итераций мы за время $O(n)$ получаем отсортированный префикс (первые $k$ элементов), а значит за $O(n^2)$ операций отсортируем весь массив целиком.
Читайте также: