Простой выбор

Это очень естественный способ сортировки, обычно он первым приходит на ум человеку, столкнувшемуся с необходимостью упорядочения таблицы. Идея его такова. Найдем в таблице элемент с наименьшим значением и поменяем его местами с первым элементом. После этого те же действия проделаем с оставшимися (без первого) N-1 элементами таблицы, затем с N-2 элементами и т. д., пока не останется один элемент - последний. Он будет наибольшим.

На Рис. 2 этот метод отображен для последовательности прямоугольников разной высоты. Два первых элемента уже упорядочены. Затем отыскивается минимальный среди остальных. Если элементы в последовательности могут быть равными, то отыскивается первый (I) среди минимальных (таким образом достигается устойчивость сортировки). Он меняется местами с третьим.

Для составления алгоритма решения этой задачи воспользуемся, как обычно, методом пошаговой детализации. Обратим внимание на то, что для получения результата нам нужно N-1 раз находить минимальное значение в таблице, длина которой уменьшается и определяется тем, в который раз мы приступили к поиску минимума. Так, в 1-й раз мы ищем минимум среди элементов A₁, A₂,..., A_N, во 2-й - среди A₂,..., A_N, в i-й - среди A_i,..., A_N. И еще один важный момент. Поскольку после нахождения минимального элемента его нужно будет поменять местами с другим элементом таблицы, то нужно запомнить номер минимального. Следовательно, первый шаг детализации можно представить таким оператором цикла:

I: = 1
пока I< =N-1
нц найти минимальный элемент и его номер в таблице A_i,..., А_N (1)
поменять местами А_i и минимальный элемент (2)
I: = I+1
кц

Еще раз приведем разработанный ранее алгоритм поиска минимума.

1. K: = I; X: = A[I]; J: = I+1
пока J< =N
нцесли A[J]< X
то X: = A[J]; K: = J
все
кц

После выполнения этих действий значением переменной Х будет значение минимального среди элементов A_i,..., A_N, а значением К - номер этого элемента. Следовательно, пункт 2 можно записать конкретнее:

поменять местами элементы A₁ и A_K (2)

Известно, что в общем случае для взаимной перестановки в памяти двух переменных нужда третья, вспомогательная:

2. C: = A[I]; A[I]: = A[K]; A[K]: = C.

Заметим, однако, что в нашей конкретной ситуации эта третья переменная не нужна, так как ее роль играет переменная Х из пункта 1:

2. A[K]: = A[I]; A[I]: = X.

Мы сэкономили одно присваивание, но это немало, так как действия выполняются в цикле многократно.

Теперь можно записать полностью алгоритм сортировки простым выбором.

алг ВЫБОР(цел N, вещтаб A[1: N])
арг A, N
рез A
начвещ X, цел I, J, К
I: = 1
пока I< =N-1
нц K: = I; X: = A[I]; J: = I+1
пока J< =N
нцесли A[J]< X
то X: = a[J]; K: = J
все
J: = J+1
кц
A[K]: = A[I]; A[I]: = X;
I: = I+1
кц
кон

На языке Паскаль оформим этот алгоритм в виде процедуры. Параметрами ее будут массив и его длина.

Процедура на Паскале

Подпрограмма на языке Бейсик

Она же на Фортране