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

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

Допустим, что два первых элемента являются упорядоченными. Теперь необходимо отыскать минимальный элемент среди остальных. Если несколько элементов последовательности оказываются равными, то следует найти первый среди минимальных элементов. Таким образом будет достигнута устойчивость сортировки. Найденный элемент из двух первых и третий по списку элемент следует поменять местами.

Для получения результата необходимо N - 1 раз найти минимальное значение в массиве, длина которого будет уменьшаться с каждым шагом на 1 (рис. 1.15).

Рис 1.15. Схема алгоритма сортировки простым выбором

Словесный алгоритм сортировки простым выбором будет следующим:

1. Начинаем сортировку с первого элемента i =1.
2. Найти минимальный элемент и его номер в массиве А ₁ , А ₂ ,...,A _N .
3. Поменять местами A _i и минимальный элемент A _k .
4. Перейти к следующему элементу i = i + 1.
5. Если рассмотрены не все N - 1 элементы, то повторить с п. 2.

Используем разработанный выше алгоритм поиска минимума и присвоим минимальной величине имя x.
Для перестановки переменных в сортируемом массиве используется операция «переприсвоения» вида A _k = A_i; A_i = х, где k - номер минимального элемента (одного из двух) на данном этапе.

Date: 2015-07-01; view: 496; Нарушение авторских прав