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