Сортировка выбором
– возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.
Идея алгоритма очень проста. Пусть имеется массив A
размером n
, тогда сортировка выбором сводится к следующему:
1. берем первый элемент последовательности A
[i
], здесь i
– номер элемента, для первого i
равен 1;
2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key
;
3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key
≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
4. увеличиваем i
на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по n
, так как элемент A
уже занимает свою позицию.
С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.
Рассмотрим работу алгоритма на примере конкретной последовательности целых чисел. Дан массив (рис. 6.2), состоящий из пяти целых чисел 9, 1, 4, 7, 5. Требуется расположить его элементы по возрастанию, используя сортировку выбором. Начнем по порядку сравнивать элементы. Второй элемент меньше первого – запоминаем это (key
=2). Далее, мы видим, что он также меньше и всех остальных, а так как key
≠1, меняем местами первый и второй элементы. Продолжим упорядочивание оставшейся части, пытаясь найти замену элементу со значением 9. Теперь в key
будет занесена 3-ка, поскольку элемент с номером 3 имеет наименьшее значение. Как видно, key
≠2, следовательно, меняем местами 2-ой и 3-ий элементы. Продолжаем расставлять на места элементы, пока на очередном шаге размер поддмассива не станет равным 1-ому.
Рисунок 6.2 – Пример сортировки выбором
Код программы на C++:
void SelectionSort(int A, int n) //сортировка выбором
Как разделить жесткий диск на разделыСегодня рассмотрим, каким способом разделить диск в Windows 10, не прибегая к стороннему программному обеспечению, ведь такая необходимость появляется...
Для чего нужна учетная запись MicrosoftВ предыдущей статья я рассказывал вам об установке , которая не сильно отличается от установки Windows XP. В этой статье мы поговорим об установке...