Сортировка выбором
При сортировке массива 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], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 2.5.
Таблица 2.5. Пример сортировки простым выбором
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 |
1 23 5 65 44 33 8 6
|
| Шаг 2 | 1 5 23 65 44 33 8 6 |
| Шаг 3 | 1 5 6 65 44 33 8 23 |
| Шаг 4 | 1 5 6 8 44 33 65 23 |
| Шаг 5 | 1 5 6 8 33 44 65 23 |
| Шаг 6 | 1 5 6 8 23 44 65 33 |
| Шаг 7 | 1 5 6 8 23 33 65 44 |
| Шаг 8 | 1 5 6 8 23 33 44 65 |
Для метода сортировки простым выбором требуемое число сравнений - nx(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(n?ln n), что в ряде случаев делает этот метод предпочтительным.
