отбор. Сортировка выбором (отбором) Работу Михайлов Илья Студент группы кабо0121

Название	Сортировка выбором (отбором) Работу Михайлов Илья Студент группы кабо0121
Дата	14.01.2022
Размер	1.76 Mb.
Формат файла
Имя файла	отбор.pptx
Тип	Документы #331208

Сортировка выбором (отбором)

Работу выполнил: Михайлов Илья Студент группы: КАБО-01-21

Определение

Сортировка выбором (отбором)– возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.
Смысл Сортировки выбором(отбором)

Смысл состоит в поиске минимального значения элемента в массиве, и перемещения этого значения в начало массива. Нужно сразу оговориться, что в данном случае можно назвать “началом” массива (куда перемещается найденное минимальное значение).

Идея алгоритма

Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

1.берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;

2.находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную min;

3.если номер первого элемента и номер найденного элемента не совпадают, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;

4.увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

“Начало”

Роль “начала” здесь играет счетчик i внешнего цикла. На каждом шаге значение элемента, номер которого отсчитывает эта переменная, считается минимальным. Вложенный цикл проводит проход по хвосту массива, вычисляя номер ячейки массива с минимальным значением (строка 18 – тернарный оператор).

Если после прохода вложенным циклом переменная min не изменилась, значит из всего хвоста массива, который обрабатывается, минимального значения нет, и элемент “начала” остается на своем месте. Иначе – значение меняется местами с найденным.

Хвост обрабатываемого массива с каждым проходом циклов уменьшается и когда достигнет конца массива, он (массив) окажется уже отсортированным. Работа алгоритма Сортировка выбором прекратится.