Алгоритм - быстрая сортировка
Cтраница 2
О, 1, 2, 3, 4, 5, 6, 7 в порядке 3, 1, 5, 0, 4, 2, 6, 7 приводит к дереву, представленному на рис. 2.20. Алгоритм сортировки вставлением, использующий древовидную структуру, очень похож на алгоритм Быстрой сортировки, описанный в разд. [16]
Тщательно сбалансированная версия йысттрой сортировки, по ясей вероятностгг, будет вытисниться ButTpct: iK) 6oitt другого метода сортировки H: S болыпинстнс ком -, к тому же бысграя сортировка широко используется как 5и ( шотечная про-сортировки и для лругнх сер иных прнложимий сортнрп кн, В с змои лс ре, а из стан дар той Гжб нтеки С - м называется qsorl ( б ьсстрая сторон port ка), иОо обычно именно алгоритм быстрой сортировки лежит в основе различных реалн-за им Й - Однако, нрсмн нылнлненин Бь1С - 1 Юй сортиройки за & иси. [17]
Для некоторых алгоритмов наихудший случаи сильно отличается от ожидаемого случая. Например, алгоритм быстрой сортировки, описанный в главе 9, имеет наихудший случаи поведения O ( N. [18]
Разновидность обменной сортировки, предложенная Лоаром. В соответствии с алгоритмом быстрой сортировки вначале определяются первый и последний элементы массива. Далее производится сравнение значений ключа сортировки записей с обеими границами при попеременном движении снизу вверх и сверху вниз до тех пор пока оказывается необходимой перестановка элементов. После этого та же самая процедура применяется к двум полученным частям и так до образования частей, содержащих всего по одному элементу. [19]
Заманчиво попытаться разработать способы улучшения быстрой сортировки: чем выше быстродействие алгоритма сортировки, тем привлекательнее выглядят возможности вычислительных систем, а быстрая сортировка представляет собой почтенный метод, который лишь усиливает это впечатление. Практически с момента опубликования Хоаром алгоритма быстрой сортировки в литературе стали регулярно появляться его усовершенствованные версии. Предлагалось и анализировалось множество идей, но при этом совсем не трудно ошибиться при оценке этих улучшений, поскольку данный алгоритм настоль хорошо сбалансирован, что эффект от усовершенствования одной части программы может послужить причиной ухудшения функционирования другой ее части. Мы детально изучим три модификации, которые существенно повышают эффективность быстрой сортировки. [20]
Это имеет смысл, так как алгоритм быстрой сортировки ни от чего не зависит. [21]
Тщательно сбалансированная версия быстрой сортировки, по всей вероятности, будет выполняться быстрее любого другого метода сортировки на большинстве компьютеров, к тому же быстрая сортировка широко используется как библиотечная программа сортировки и для других серьезных приложений сортировки. В самом деле, сортировка из стандартной библиотеки C называется qsort ( б [ ыстрая ] сортировка), ибо обычно именно алгоритм быстрой сортировки лежит в основе различных реализаций. Однако, время выполнения быстрой сортировки зависит от организации входных данных и колеблется между линейной и квадратичной зависимостью от количества сортируемых элементов и пользователи иногда бывают неприятно удивлены неожиданно неудовлетворительными, неприемлемыми результатами сортировки некоторых видов входных данных, особенно когда используются хорошо отлаженные версии этого алгоритма. Если приложение работает настолько плохо, что возникает подозрение в наличии дефектов в реализации быстрой сортировки, то сортировка методом Шелла может оказаться более удачным выбором, обеспечивающим лучший результат при меньших затратах на реализацию. Следует отметить, что в случае особо крупных файлов быстрая сортировка выполняется примерно в пять-десять раз быстрее сортировки методом Шелла, при этом на некоторых видах файлов, довольно часто встречающихся на практике, может быть достигнута еще большая эффективность данного вида сортировки. [22]
 |
Время пузырьковой сортировки 20 000 элементов. [23] |
В табл. 9.2 приведено время работы программы на компьютере с процессором Pentium-133 для пузырьковой сортировки 20 000 элементов в зависимости от степе ни первоначальной упорядоченности списка. Из таблицы видно, что пузырьковая сортировка выполняется достаточно хорошо только тогда, когда список изначально отсортирован. Алгоритм быстрой сортировки, описанный далее, может сортировать тот же самый список из 20 000 элементов приблизительно за 0 05 с, если элементы изначально расположены беспорядочно. Пузырьковая сортировка может справиться с этой задачей за такое же время, если список почти полностью отсортирован. [24]
Алгоритмы построения выпуклой оболочки, основанные на методе разделяй и властвуй, разбивающие исходное множество точек на две части, строящие выпуклую оболочку для каждой из этих частей и затем объединяющие их за линейное время, являются геометрическими аналогами алгоритма сортировки слиянием. Алгоритм, строящий выпуклую оболочку в реальном времени, является аналогом алгоритма сортировки вставками. Аналоги алгоритма быстрой сортировки обсуждались в разд. [25]
Если массив содержит не более одного элемента, то он упорядочен. Этот алгоритм не использует дополнительного массива и требует в среднем приблизительно п Iog2 n сравнений и столько же перемещений элементов. Правда, это лишь среднее число: в худшем случае число сравнений может достигать п ( п - 1) / 2; кроме того, алгоритм быстрой сортировки содержит рекурсии. [26]
Программа 10.1 представляет полную реализацию этого метода. Применяемый в ней процесс разбиения по существу лишь немногим отличается от разбиения, реализованного в программе 7.2, за исключением того, что в рассматриваемом случае в качестве разделяющего элемента используется число 2й, а не некоторый ключ из файла. Поскольку числа 2й может и не быть в файле, то нет гарантии того, что конкретный элемент будет помещен в свою окончательную позицию в процессе разбиения. Рассматриваемый алгоритм отличается от алгоритма быстрой сортировки, поскольку рекурсивные вызовы выполняются для ключей, имеющим на 1 бит меньше. Это различие существенно влияет на эффективность алгоритма. Например, если имеет место вырожденное разбиение файла из N элементов, то произойдет рекурсивный вызов для подфайла размером N для ключей, имеющим размер на 1 разряд меньше. Следовательно, число таких вызовов ограничено количеством разрядов в ключе. В противоположность этому, последовательное использование разделяющих значений, взятых не из самого файла в условиях стандартной быстрой сортировки может привести к возникновению бесконечного рекурсивного цикла. [27]
Да, согласованная схема для параметров-массивов придает процедурам и функциям достаточную гибкость, делая их нечувствительными к числу компонентов фактического параметра. Вместе с тем данный механизм обладает и существенным недостатком: число компонентов массива в момент обращения должно быть фиксированным. Это служит препятствием при решении некоторых задач. Так, в частности, при программировании алгоритма быстрой сортировки разбиение массива на части зависит от значений компонентов и, следовательно, становится известным только в процессе выполнения программы. [28]
Страницы: 1 2