Идея метода. Сначала выбирается минимальный (или максимальный) элемент в массиве и меняется местами с первым (последним) элементом массива. Минимальный элемент теперь стоит на своем месте, и в дальнейшем исключается из рассмотрения. То же самое повторяется для "усеченного" массива со 2-го по n-ый элемент.
Действия повторяются до тех пор, пока в "усеченном" массиве не останется один последний элемент.
Основные блоки алгоритма:
нахождение среди неупорядоченных элементов минимального (максимального);
обмен местами значений "ячеек", в которых находятся найденный минимальный элемент и первый элемент среди неупорядоченных.
То есть, при сортировке массива a[1], a[2], ..., a[n] среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение.
Работа алгоритма иллюстрируется примером в таблице
Пример сортировки методом простого выбора
|
Начальное состояние массива |
12 18 15 14 10 22 15 |
|
Шаг 1 |
10 18 15 14 12 22 15 |
|
Шаг 2 |
10 12 15 14 18 22 15 |
|
Шаг 3 |
10 12 14 15 18 22 15 |
|
Шаг 4 |
10 12 14 15 18 22 15 |
|
Шаг 5 |
10 12 14 15 15 22 18 |
|
Шаг 6 |
10 12 14 15 15 18 22 |
Чтобы совершить обмен, не важны значения минимального элемента и первого элемента среди неупорядоченных, а важны номера (индексы) этих элементов.
Если первый элемент среди неупорядоченных окажется минимальным, то он просто обменивается значением сам с собой - дополнительную проверку добавлять нецелесообразно.
Чтобы поменять местами значения двух переменных, потребуется одна вспомогательная переменная.
Алгоритм использует вложенные циклы. Внешний цикл (счетчик шагов) последовательно выбирает номер элемента массива, куда следует записывать найденный в неупорядоченной части массива минимальный элемент. Внутренний цикл перебирает номера неупорядоченных элементов при поиске минимального элемента. Для внешнего цикла достаточно шагов на один меньше, чем элементов в массиве.
Для метода сортировки простым выбором требуемое число сравнений - nx(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(n?ln n), что в ряде случаев делает этот метод предпочтительным.
