Cтраница 3
Лемма 10.2. Двоичная быстрая сортировка в среднем производит проверку N lg / V разрядов при сортировке ключей, состоящих их битов, принимающих случайное значение. [31]
Внутренний цикл быстрой сортировки увеличивает значение указателя на единицу и сравнивает элементы массива с конкретным фиксированным значением. Именно эта простота и делает быструю сортировку быстрой: трудно себе представить более короткий внутренний цикл в алгоритме сортировки. [32]
Семейство алгоритмов быстрой сортировки, рассмотрен ное в главе 7, О НОЕЕЭНО на опера ц Et и яыборки; на-ьожаенис k - ro м и Ff к мольного элемента в файле. Ми убс-лнлнсь в точ, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую НСй наименьших элементов, и часть, содержащую jV - Jt больших по значению элементов, В этой главе ся семейстйо алгоритмов сортироьки, в основе лежит вспомогательный процесс, известный как т.е.. [33]
Семейство алгоритмов быстрой сортировки, рассмотренное в главе 7, основано на операции выборки: нахождение fc-ro минимального элемента в файле. Мы убедились в том, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую все k наименьших элементов, и часть, содержащую N - k больших по значению элементов. В этой главе исследуется семейство алгоритмов сортировки, в основе которых лежит вспомогательный процесс, известный как слияние, т.е., объединение двух отсортированных файлов в один файл большего размера. Слияние является основой для простого алгоритма сортировки типа разделяй и властвуй ( см. раздел 5.2), а также для его двойника - алгоритма восходящей ( снизу-вверх) сортировки слиянием, при этом оба из них достаточно просто реализуются. [34]
Второй вариант быстрой сортировки более общий. В примере 15.10 процедура быстрой сортировки заключена в глобальный модуль. Он взаимодействует с подлежащей сортировке структурой данных с помощью двух процедур, одна из которых осуществляет сравнение двух элементов структуры, а другая - обмен элементов. Этот вариант - шаг вперед, но его общность все еще недостаточна. [35]
Разделение в быстрой сортировке начинается с выбора ( произвольного) разделяющего элемента. Затем выполняется просмотр слева с пропуском элементов с меньшими значениями и справа с пропуском элементов с большими значениями, обмен элементов, на которых просмотры остановились, после чего просмотр продолжается до тех пор, пока значения указателей не совпадут. Мы начинаем с просмотра слева и останавливаемся на S, затем проводится просмотр справа, который останавливается на элементе А, после чего производится обмен местами элементов S и А. [36]
Какими преимуществами обладает Быстрая сортировка по сравнению с методом пузырька. На первый взгляд может показаться, что небольшие изменения порядка перестановки ключей только заставляют нас писать значительно более трудные программы. [37]
В худшем случае Быстрая сортировка невыгодна потому, что предположения относительно среднего значения ставятся особенно неудачными. [38]
Тщательно сбалансированная версия быстрой сортировки, по всей вероятности, будет выполняться быстрее любого другого метода сортировки на большинстве компьютеров, к тому же быстрая сортировка широко используется как библиотечная программа сортировки и для других серьезных приложений сортировки. В самом деле, сортировка из стандартной библиотеки C называется qsort ( б [ ыстрая ] сортировка), ибо обычно именно алгоритм быстрой сортировки лежит в основе различных реализаций. Однако, время выполнения быстрой сортировки зависит от организации входных данных и колеблется между линейной и квадратичной зависимостью от количества сортируемых элементов и пользователи иногда бывают неприятно удивлены неожиданно неудовлетворительными, неприемлемыми результатами сортировки некоторых видов входных данных, особенно когда используются хорошо отлаженные версии этого алгоритма. Если приложение работает настолько плохо, что возникает подозрение в наличии дефектов в реализации быстрой сортировки, то сортировка методом Шелла может оказаться более удачным выбором, обеспечивающим лучший результат при меньших затратах на реализацию. Следует отметить, что в случае особо крупных файлов быстрая сортировка выполняется примерно в пять-десять раз быстрее сортировки методом Шелла, при этом на некоторых видах файлов, довольно часто встречающихся на практике, может быть достигнута еще большая эффективность данного вида сортировки. [39]
Наиболее благоприятный для быстрой сортировки случай имеет место, когда на каждой стадии разбиения файл делится на две равные части. [40]
Рекурсивный стек для быстрой сортировки не становится больше для файлов с произвольной организацией, но в то же время он может потребовать дополнительного пространства при работе с вырожденными файлами. [41]
Заметное повышение эффективности быстрой сортировки следует из того факта, что рекурсивная программа гарантировано вызывает сама себя для работы со множеством подфайлов небольших размеров. Следовательно, когда она сталкивается с подфаилами небольших размеров, она обязана использовать по возможности самый лучший метод работы с ними. [42]
Подфайлы в условиях быстрой сортировки обрабатываются независимо друг от друга. На этой диаграмме показан результат разбиения каждого подфайла в процессе сортировки 200 элементов с отсечением файлов размером 15 и меньше. [43]
Что касается реализации быстрой сортировки, ориентированной на массивы, то простого способа устойчивого разбиения файлов не видно, так что возможность положительного решения проблемы устойчивости исключается еще до того, как рекурсия вступит в дело. [44]
Другие варианты программ быстрой сортировки обсуждаются в статье R. [45]