Следующий алгоритм сортировки, который я буду обсуждать, — это сортировка выбором. В предыдущем посте пузырьковая сортировка работала, помещая наибольшее значение в конец, многократно меняя местами значения, если критерий выполнялся. Сортировка выбором работает, находя сначала наименьшие значения и помещая их в начало. Однако на каждой итерации выполняется максимум один обмен. Это отличается от сортировки пузырьком, где диапазон внутреннего цикла потенциально равен количеству выполненных обменов. Временная сложность O(n²).
Сортировка выбором работает с использованием вложенного цикла. Индекс минимального значения отслеживается на каждой итерации внутреннего цикла. Когда достигается конец внутреннего цикла, выполняется обмен. Этот алгоритм сортировки сложно оптимизировать, но его можно немного улучшить. Его можно оптимизировать, проверив, равен ли минимальный индекс индексу внешнего цикла. Если это так, мы знаем, что наш начальный индекс также был минимальным индексом, что означает, что обмен не должен происходить. Это приводит к улучшению использования памяти из-за меньшего количества операций записи.
Трудно придумать действительно хороший вариант использования этого алгоритма, но, тем не менее, он существует не просто так.
