Алгоритм простого выбора

Этот алгоритм является непосредственной реализацией идеи сортировки выбором: из ещё не отсортированных записей выбирается минимальная (максимальная) и добавляется последней (первой) к уже отсортированным записям.

На рис. 1 схематично представлен i -й шаг алгоритма. К этому шагу первые i записей исходного массива уже отсортированы по возрастанию и на рисунке помечены серым цветом. Среди оставшихся (n – i) записей k (j), j = i, …, n, необходимо выбрать минимальный элемент и сохранить его индекс во вспомогательной переменной temp. С этой целью переменной temp присваивается значение i. Затем последовательно сравниваются k (j), j = i + 1, …, n – 1, со значением k (temp). В случае если k (j) < k (temp), переменной temp присваивается значение j. Шаг алгоритма завершается перестановкой местами элементов k (i) и k (temp).

Пример работы алгоритма сортировки простым выбором последовательности 6, 1, 8, 2, 5, 3, хранящейся в массиве, представлен на рис. 2.

Реализация на языке С++ алгоритма сортировки простым выбором на примере хранящихся n записей типа T в массиве k представлена в листинге 1. Комментарии в правой части листинга содержат число выполнения соответствующей строки алгоритма и поясняют определение его вычислительной сложности. В формулах через ui обозначено число записей k (j), j = i – 1, i – 2,..., 0, которые больше записи k (i), то есть составляют с ней инверсию.