Cтраница 2
Очень быстрые сортировки для малых списков с каким-нибудь неизвестным упорядочением могут использоваться в комбинации с эффективным методом для случайных данных с большим N. Помимо поиска комбинации аналитику или программисту никогда не следует пренебрегать возможностью самому создать новый и лучший метод сортировки. [16]
Быструю сортировку можно еще улучшить, используя для расщепления таблицы медиану малой случайной выборки из k имен. [17]
Быструю сортировку более корректно было бы назвать алгоритмом типа разделяй и властвуй: в рекурсивных реализациях после активизации программы большая часть работы выполняется перед рекурсивными вызовами. С другой стороны, рекурсивная сортировка слиянием еще больше выдержана в духе принципа разделяй и властвуй: прежде всего, файл делится на две части, затем обработке ( воздействию власти) по отдельности подвергаются обе части. Сначала сортировке слиянием подвергаются файлы небольших размеров, в заключение обработке подвергается самый большой подфайл. Быстрая сортировка начинается с обработки наибольшего подфайла и завершается обработкой подфайлов небольших размеров. Интересна провести сравнение этих алгоритмов в контексте аналогии с управлением коллективом сотрудников, приводимой в начале настоящей главы: быстрая сортировка соответствует тому, что каждый руководящий работник затрачивает свои усилия на то, чтобы правильно разбить задачу на подзадачи, так что работа будет успешно выполнена, если успешно выполнены все подзадачи, в то время как сортировка слиянием соответствует тому, что каждый руководящий работник выполняет быструю произвольную разбивку задачу напополам, а затем затрачивает все свои усилия на то, чтобы преодолеть последствия подобных действий после того, как соответствующие подзадачи будут решены. [18]
Лучше всего быстрая сортировка описывается как рекурсивная процедура. Основная идея состоит в том, чтобы разбить начальное множество, которое должно быть рассортировано с помощью перегруппировки, на две группы: все те элементы, которые меньше некоторой произвольно взятой из этого множества величины, и все те элементы, которые больше или равны этой величине. Затем аналогичный процесс разбиения применяется по очереди к двум подмножествам до тех пор, пока каждое подмножество не будет содержать один элемент. Когда все подмножества будут разбиты, начальное множество считается рассортированным. [19]
Алгоритм быстрой сортировки обладает и другими весьма привлекательными особенностями: он принадлежит к категории обменных ( in-place) сортировок ( т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренний циклы. Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется TV2 операций, он хрупок в том смысле, что даже простая ошибка в реализации может пройти незамеченной и вызвать ошибки в работе алгоритма на некоторых видах файлов. [20]
Работа быстрой сортировки проста для понимания. Алгоритм был подвергнут тщательному математическому анализу, и можно дать достаточно точную оценку его эффективности. [21]
Модификация быстрой сортировки, предусматривающая вычисление медианы из трех элементов ( в частности, с использованием среднего элемента) обеспечивает приличные результаты в плане, придания процессу разделения большей устойчивости. Особенно хорошо этот метод проявляет себя при сортировке вырожденных файлов, показанных на рис. 7.4. Другой вариант, позволяющий достичь тех же целей, - использование случайного разделяющего элемента. [22]
Алгоритм быстрой сортировки можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива. [23]
Обеспечение быстрой сортировки и соответствующего лечения в амбулаторных кабинетах пациентов, которые могут быть заражены туберкулезом. Сортировка пациентов в отделениях амбулаторной и скорой помощи должна предполагать энергичные усилия по быстрому выявлению пациентов с активной формой туберкулеза. Медработники, которые первыми входят в контакт с опасностью туберкулеза в учреждениях, обслуживающих население, должны быть обучены соответствующему проведению опроса, облегчающему обнаружение пациентов с признаками и симптомами предполагаемого туберкулеза. Такие пациенты должны быть быстро обследованы для того, чтобы сократить до минимума время их пребывания в помещениях амбулаторной помощи. После того как у этих пациентов проведено диагностическое обследование, должны быть предприняты меры предосторожности против туберкулеза. [24]
Ценность быстрой сортировки можно увеличить, определив, когда часть становится слишком маленькой для того, чтобы продолжение построения частей было выгодным. Эта часть потом упорядочивается другим методом. Соответствующий размер минимальной записи зависит от конкретной машины. В качестве другого приемлемого способа Синглтон выбрал просеивание. Процесс, которым упорядочивается данная часть, никак не связан с другими частями, так что никаких изменений в методе не происходит за исключением дополнительной проверки длины части и перехода к другому способу. В любом случае надо в некоторой форме проверять длину частей, поскольку необходимо проверять части на правильность. Все опубликованные алгоритмы кроме алгоритма Синглтона являются быстрой сортировкой в чистом виде, за исключением ускоренной сортировки, которая исключает, части, состоящие менее чем из трех элементов. [25]
Создание быстрой сортировки по принципу один процессор для каждой порции неприемлемо как с точки зрения интересов сортировки, так и с точки зрения пропускной способности системы. Допустим, что две 32-процессорные системы могут выполнить 4032 сравнений за то же время, за какое один процессор выполнит 126 сравнений. Время сортировки, требующей 4000 сравнений ( по 125 на один процессор), может быть меньше, чем у быстрой сортировки, требующей в целом 384 сравнения. [26]
Модификация быстрой сортировки для многопроцессорной среды предполагает использование ня каждом просмотре двух основ, таким образом, второй процессор может участвовать в исходном разделении списка на части. Список элементов, меньших одной границы, группируется у вершины; список элементов, больших другой границы, - внизу. Опубликованные результаты не позволяют сделать заключения о том, что этот подход быстрее быстрой сортировки. [27]
Mctoi быстрой сортировки Oipoip-ямма 7.11 иьшо. [28]
Лемма 7.1. Быстрая сортировка в наихудшем случае выполняет примерно TV2 / 2 операций сравнения. [29]
Лемма 7.2. Быстрая сортировка в среднем выполняет 2N nN операций сравнения. [30]