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

ОГЛАВЛЕНИЕ

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

Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком,  а именно,  время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными,  а начиная с некоторой величины они будут слишком медленными, чтобы их можно было использовать на практике.  Каждый программист слышал или рассказывал  "страшные"
истории о "сортировке,  которая выполнялась три дня". К сожалению эти истории часто не являлись выдумкой.

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

В этой главе будут рассмотрены две очень хорошие сортировки. Первая носит название сортировки Шелла, а вторая называется быстрой сортировкой,  алгоритм которой признан наилучшим.  Эти сортировки выполняются очень быстро.