|
Страница 8 из 60
Усовершенствованные алгоритмы сортировки
Все рассматриваемые до сих пор алгоритмы сортировки обладают
очень серьезным недостатком, а именно, время их выполнения про-
порционально квадрату числа элементов. Для больших объемов данных
эти сортировки будут медленными, а начиная с некоторой величины
они будут слишком медленными, чтобы их можно было использовать на
практике. Каждый программист слышал или рассказывал "страшные"
истории о "сортировке, которая выполнялась три дня". К сожалению
эти истории часто не являлись выдумкой.
Если сортировка выполняется слишком долго, то причиной этого
может быть используемый алгоритм. Однако, первая реакция на такое
поведение сортировки выражается словами: "Давай напишем программу
на ассемблере". Хотя использование ассемблера почти всегда позво-
ляет повысить быстродействие программы в некоторое число раз с
постоянным коэффициентом, но если выбранный алгоритм не является
достаточно хорошим, то сортировка вне зависимости от оптимальнос-
ти кода по-прежнему будет выполняться долго. Следует помнить, что
при квадратичной зависимости времени выполнения программы от чис-
ла элементов массива повышение оптимальности кода или повышение
быстродействия ЭВМ приведет лишь к незначительному улучшению,
поскольку время выполнения программы будет увеличиваться по экс-
поненте. /Кривая, показанная на рис.1 лишь слегка сместится впра-
во, однако ее вид не изменится/. Следует помнить, что если какая-
либо программа, написанная на языке Турбо Паскаль, выполняется
недостаточно быстро, то она не станет выполняться достаточно
быстро, если ее написать на ассемблере. Решение лежит в использо-
вании лучшего алгоритма сортировки.
В этой главе будут рассмотрены две очень хорошие сортировки.
Первая носит название сортировки Шелла, а вторая называется быст-
рой сортировкой, алгоритм которой признан наилучшим. Эти сорти-
ровки выполняются очень быстро. |