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