Сортировка методом простого выбора

Этот метод сортировки обычно применяется для массивов, не содержащих повторяющихся элементов. Для достижения поставленной цели можно действовать следующим образом:

1. выбрать максимальный элемент массива;

2. поменять его местами с последним элементом (после этого наибольший элемент будет стоять на своем месте);

3. повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1) - м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.

Всего потребуется n-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.

Рассмотрим этот процесс на примере. Пусть исходный массив а состоит из 10 элементов и имеет вид:

5 13 7 9 1 8 16 4 10 2

После сортировки массив должен выглядеть так:

1 2 4 5 7 8 9 10 13 16

Процесс сортировки представлен ниже. Максимальный элемент текущей части массива заключен в кружок, а элемент, с которым происходит обмен, - в квадратик. Скобкой помечена рассматриваемая часть массива.

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент -16 (он стоит на седьмом месте); поменяем его местами с последним элементом.

5 13 7 9 1 8 16 4 10 2

Максимальный элемент помещен на свое место.

2-й шаг: рассмотрим часть массива с первого до девятого элемента. Максимальный элемент этой части стоит на втором месте и имеет значение 13. Поменяем его местами с последним элементом этой части.

5 13 7 9 1 8 2 4 10 16

Отсортированная часть массива состоит теперь уже из двух элементов.

3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент (его значение 10) и последний элемент этой части (его значение 4).

5 10 7 9 1 8 2 4 13 16