Разбор алгоритмов сортировки мы начнем с самых простых и пойдём на усложнение. Сегодня мы рассмотрим простые алгоритмы сортировки. Эти алгоритмы и правда являются довольно простыми, как в понимании, так и в реализации. Однако, в данном случае, за простоту мы платим сложностью. К сожалению, эти алгоритмы не являются эффективными и имеют высокую вычислительную сложность.
Сортировка вставками
При этой сортировке входной массив последовательно перебирается от начала до конца. Каждый следующий выбранный элемент перемещается по массиву назад таким образом, чтобы он оказался между двумя элементами так, чтобы предыдущий был меньше выбранного числа, а следующий был больше. Соответственно, если при выборе элемента он сразу больше предыдущего, то его перемещать не нужно.
Один из вариантов реализации этого алгоритма будет выглядеть вот так:
А теперь о сложности этого алгоритма.
Сложность по времени:
Худшее время: O(n2) для сравнений и перестановок;
Среднее время: Θ(n2) для сравнений и перестановок;
Лучшее время: Ω(n) для сравнений и Ω(1) для перестановок.
Сложность по требуемой памяти: O(n) плюс 1 ячейка памяти для буферизации выбранного элемента.
Сортировка выбором
Алгоритм сортировки выбором выглядит следующим образом. Сначала делается полный проход по массиву в поисках наименьшего элемента. Далее найденный минимальный элемент меняется местами с элементом, который стоит на нулевой позиции. Ну и дальше эти действия повторяются для оставшегося массива, т. е. ищется минимальный элемент в оставшемся подмассиве и ставится на 1 позицию и так далее пока массив не будет полностью отсортирован.
Один из вариантов реализации выглядит вот так:
Вычислительной сложность этот алгоритм не блещет, как и предыдущий.
Сложность по времени:
Худшее время: O(n2);
Среднее время: Θ(n2);
Лучшее время: Ω(n2).
Сложность по требуемой памяти:
O(n) плюс 1 ячейка памяти для буферизации выбранного элемента.
У этого алгоритма есть вполне логичная модификация и называется она «двусторонняя сортировка выбором». Ведь если мы все равно идем по массиву, почему бы сразу не искать минимальный и максимальный элемент и вставлять эти элементы в конец и начало массива?
Кажется, таким образом мы ускоримся в 2 раза. Однако нет. Количество перестановок и сравнений останется прежним, а, значит, и вычислительная сложность алгоритма не особо изменится.
На этом мы пока остановимся. Конечно, к простым сортировкам можно также отнести всеми любимую сортировку пузырьком. В следующей статье мы как раз и поговорим о пузырьковой сортировке и ее модификациях.
Узнать больше о других видах сортировок вы можете из материалов блога:
