2. Алгоритм выбора (SelectionSort)

Идея этого алгоритма еще проще. Найдем минимальный элемент массива и поменяем его местами с первым элементом. Затем повторим ту же процедуру, начиная со второго элемента массива, затем начиная с третьего и т.д. После n–1проходов все элементы станут на места.

3. Алгоритм вставок (InsertionSort)

Идея заключается в следующем. Пусть к некоторому моменту работы алгоритма первые kэлементов массива уже отсортированы, т.е. расположены по возрастанию. На очередном проходе постараемся добиться, чтобы стали отсортированнымиk+1элементов. Для этого запомним значение элементаa_k+1в рабочей переменнойrи будем сравниватьrсо значениями элементовa_k,a_k–1,a_k–2и т.д. Если значение сравниваемого элемента большеr, то этот элемент перемещается на одну позицию правее. Сравнения продолжаются, пока не будет найдено место, куда должен быть помещен элементr(это случится либо когда очередной сравниваемый элемент меньше или равенr, либо когда мы дойдем до начала массива).

Таким образом, на очередном проходе отсортированная часть массива удлиняется на 1 элемент. Начав со значения k = 1, можно заn–1проход отсортировать весь массив.

Алгоритм вставок можно немного улучшить, если выбирать место для вставки k+1-го элемента не последовательным просмотром элементов отkдо1, а бинарным поиском по уже отсортированной части масива (т.е. сравнитьrс элементомj = (k+1) div 2, затем продолжить поиск на одном из интервалов[1 .. j–1]или[j+1 .. k]и т.д.). Этот подход, называемый алгоритмомбинарных вставок, позволяет существенно сократить число сравнений, но, к сожалению, не влияет на число перестановок.

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

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

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

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