Алгоритм - быстрая сортировка
Cтраница 1
Алгоритм быстрой сортировки можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива. [1]
Алгоритм быстрой сортировки обладает и другими весьма привлекательными особенностями: он принадлежит к категории обменных ( in-place) сортировок ( т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренний циклы. Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется TV2 операций, он хрупок в том смысле, что даже простая ошибка в реализации может пройти незамеченной и вызвать ошибки в работе алгоритма на некоторых видах файлов. [2]
Семейство алгоритмов быстрой сортировки, рассмотренное в главе 7, основано на операции выборки: нахождение fc-ro минимального элемента в файле. Мы убедились в том, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую все k наименьших элементов, и часть, содержащую N - k больших по значению элементов. В этой главе исследуется семейство алгоритмов сортировки, в основе которых лежит вспомогательный процесс, известный как слияние, т.е., объединение двух отсортированных файлов в один файл большего размера. Слияние является основой для простого алгоритма сортировки типа разделяй и властвуй ( см. раздел 5.2), а также для его двойника - алгоритма восходящей ( снизу-вверх) сортировки слиянием, при этом оба из них достаточно просто реализуются. [3]
Семейство алгоритмов быстрой сортировки, рассмотрен ное в главе 7, О НОЕЕЭНО на опера ц Et и яыборки; на-ьожаенис k - ro м и Ff к мольного элемента в файле. Ми убс-лнлнсь в точ, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую НСй наименьших элементов, и часть, содержащую jV - Jt больших по значению элементов, В этой главе ся семейстйо алгоритмов сортироьки, в основе лежит вспомогательный процесс, известный как т.е.. [4]
Многие программисты выбирают именно алгоритм быстрой сортировки, поскольку во многих случаях он обеспечивает хорошую производительность. [5]
 |
Время быстрой сортировки одного миллиона элементов. [6] |
Вы можете улучшить работу алгоритма быстрой сортировки, останавливая рекурсию перед тем, как подсписки будут пусты, и использовать сортировку выбором, чтобы завершить процесс. В табл. 9.3 приведено время выполнения программы для ускоренной сортировки миллион а элементов на компьютере с процессором Pentium-133, если останавливать сортировку при достижении подсписками определенного размера. [7]
Сортирует произвольный массив, используя алгоритм быстрой сортировки. [8]
Примером может служить поиск осевого элемента в алгоритме быстрой сортировки. [9]
Очередность, в которой производится обработка подфайлов, не препятствует корректному выполнению алгоритма быстрой сортировки и не приводит к увеличению времени выполнения сортировки, однако может повлиять на размеры стека магазинного типа, положенного в основу рекурсивной структуры. В рассматриваемом случае первым обработке подвергается меньший из подфайлов, образованных в результате каждого разделения. [10]
Эта программа осуществляет сортировку массива, состоящего из 10 000 целых чисел, используя алгоритм быстрой сортировки [76], В программе используется рекурсивная процедура. [11]
При истолковании данного метода следует соблюилть осторожность, ибо сортировку вставками скорее всего бу-дет работать, даже если алгоритм быстрой сортировки содержит фатальную ошибку, из-за которой эта сортировку просто фу и км и он кровать не будет. Только резкое возраста н кс эятрлт ресурсов может СЛУЖИТЕ. Рисунок 7 9 иллюстрирует этот гтрсшесс tta примере крупного файла. [12]
При использовании данного метода следует соблюдать осторожность, ибо сортировка вставками скорее всего будет работать, даже если алгоритм быстрой сортировки содержит фатальную ошибку, из-за которой эта сортировка просто функционировать не будет. Только резкое возрастание затрат ресурсов может служить сигналом о том, что что-то не в порядке. [13]
В этом случае скорость выполнения сортировки подсчетом может быть ниже, чем скорость O ( N logN) алгоритмов быстрой сортировки. [14]
 |
К дереву на рис добавлен 0 на соответствующее. [15] |
Страницы: 1 2