Энциклопедия Turbo Pascal. Главы 1-4
Страница 8. Усовершенствованные алгоритмы сортировки


Усовершенствованные алгоритмы сортировки

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

 
« Предыдущая статья