Общая характеристика простых алгоритмов

Теоретическое и экспериментальное сравнение трех описанных алгоритмов друг с другом показывает, что алгоритм пузырька является самым медленным из них. Это можно объяснить большим числом перестановок элементов: для того, чтобы всего лишь поменять местами два соседних элемента, нужно выполнить целых 3 присваивания. Алгоритмы выбора и вставки работают в 1,5 – 2 раза быстрее и показывают схожие друг с другом результаты по скорости, за исключением одного важного случая. Если исходный массив оказывается уже «почти» сортированным (т.е. лишь небольшое количество элементов расположены не там, где им следовало бы быть), то алгоритм вставок оказывается во много раз быстрее других. В том крайнем случае, когда исходный массив полностью сортирован, алгоритм вставок выполняет всего лишь один проход по массиву, т.е. работает за линейное время. Для двух других алгоритмов факт сортированности может повлиять на уменьшение числа перестановок, но практически не влияет на число сравнений.

Этим преимуществом алгоритма вставок не стоит пренебрегать, поскольку на практике достаточно часто встречается ситуация, когда нужно повторно отсортировать массив, который ранее уже был сортирован, но после этого претерпел небольшие изменения, нарушившие порядок элементов.

Однако, подсчитав число итераций циклов, можно показать, что для всех простых алгоритмов сортировки имеет место оценка эффективности T(n) = O(n²) как для максимального, так и для среднего времени. Плохо это или хорошо? Квадратичная оценка была бы хороша для алгоритма, который должен выполняться, скажем, раз в сутки или еще реже, при этом для значений n, не превышающих нескольких сотен или, в крайнем случае, тысяч. Однако для задач сортировки характерна гораздо большая частота выполнения, а зачастую и гораздо большие значения n. Уже для n = 100 000 квадратичный алгоритм потребует выполнить около 10 миллиардов итераций, что вряд ли можно считать приемлемым. Поэтому в следующих параграфах будут рассмотрены усовершенствованные алгоритмы, значительно более сложные, но зато обеспечивающие во много раз большую скорость сортировки.