Еще одна сортировка, не сильно отличающаяся по времени работы от изученных ранее. Алгоритм сортировки выделением достаточно прост и, наверное, это самый интуитивно понятный алгоритм.
Описание:
Как обычно рассмотрим алгоритм сортировки по возрастанию.
В алгоритме выделением мы находим самый маленький элемент входного массива и меняем его местами с элементом в начале, после исключаем данный элемент из поиска и еще раз ищем минимальный элемент, но уже размещаем его после предыдущего минимального и так до тех пор, пока не пройдем по всем элементам массива. Отсюда и происходит название «Сортировка выделением» - на каждой итерации работы алгоритма мы выделяем минимальный элемент из рассматриваемых в данный момент.
По традиции блок-схема алгоритма:
И конечно же реализация на Python:
Алгоритмическая сложность:
Временная сложность О(n²), рассчитывается по аналоги с сортировкой вставками. По памяти нашему алгоритму требуется место для запоминания массива из N элементов, дополнительная ячейка памяти не требуется. Итого по памяти О(1) – для всего массива
Построим график зависимости времени выполнения от количества элементов и сравним его с ранее изученными.
Алгоритм получается быстрее Сортировки вставками за счет того что в нем не требуется производить сдвиг массива вправо, а просто произвести обмен элементов местами.