Быстрая сортировка

Cтраница 1

Быстрая сортировка) В примерах и упражнениях главы 6 мы обсуждали алгоритмы сортировки, такие, как пузырьковая или блочная сортировка. Мы представим вам теперь рекурсивный алгоритм сортировки, называемый быстрой сортировкой. [1]

Эмпирическое исследование алгоритмов быстрой сортировки. [2]

Быстрая сортировка нашла широкое применение в связи с тем, что она успешно протекает в различных ситуациях. Другие методы хорошо работают в некоторых специальных случаях, которые время от времени встречаются на практике, но быстрая сортировка успешно решает гораздо большее число сортировочных задач, чем это можно сделать с применением других методов, а ее быстродействие зачастую гораздо выше, чем в условиях применения альтернативных подходов. В табл. 7.1 представлены эмпирические результаты, которые могут служить подтверждением некоторых из сделанных выше выводов. [3]

Быстрая сортировка делит список на два так, что все элементы одного предшествуют всем элементам другого. [4]

Первый этап Быстрой сортировки. Смысл переменных / и / ясен из алгоритма Быстрой сортировки. [5]

Быстрая сортировка в принципе проста, однако если алгоритм должен быть итеративным, а не рекурсивным, то над написанием программы для него придется поразмыслить. [6]

Время пузырьковой сортировки 20 000 элементов. [7]

Быстрая сортировка ( quicksort) - это рекурсивный алгоритм, который использует подход разделяй и властвуй. Даже если список элементов, который нужно отсортировать, имеет не который минимальный размер, процедура быстрой сортировки делит его на два подсписка, а затем рекурсивно вызывает себя для их сортировки. [8]

Быстрая сортировка - эффективный способ упорядочения, оя гораздо быстрее, чем сортировка вставками, описанная в упр. Со всеми алгоритмами сортировки связана Следующая проблема: при увеличении числа сортируемых объектов в два раза, объем вычислений возрастает более чем в два раза. Сортировка двухсот объектов потребует более чем в два раза большего времени, чем сортировка ста. [9]

Быстрая сортировка имеет смысл, когда число сортируемых объектов переваливает за несколько десятков. [10]

Быстрая сортировка основана на перемещении каждого объекта на его конечную позицию. Конечная позиция элемента определяется тем, что все объекты ниже - не больше, чем он, а все, лежащие выше, - не меньше. После передвижения элемента на конечную позицию совокупность данных делится на две части: на часть, которая лежит ниже, я часть, располагающуюся выше. Затем процедура быстрой сортировки вызывает саму себя для обработки этих двух частей. Ниже приведен первый шаг декомпозиции программы быстрой сортировки на псевдокоде. [11]

Быстрая сортировка - это метод, ориентированный на использование дерева, хотя связь между двоичным деревом и алгоритмом сортировки в нем не столь явная, как в турнирной или двоичной сортировке. [12]

Быстрая сортировка может использоваться в комбинированном алгоритме, чтобы сократить части до заранее определенного размера, после чего они упорядочиваются другим методом, более эффективным для малых списков. [13]

Быстрая сортировка последовательно просматривает список в поисках величины, большей выбранной основы. Когда таковая найдена, происходит рбмен с меньшей величиной. Поиск меньшей и поиск большей величин идут навстречу друг другу, и при встрече просмотр заканчивается. Если есть один лист для поиска снизу-вверх и один для поиска сверху-вниз, листание будет возникать лишь при пересечении границ листа. Листание между просмотрами Зависит от размеров физической памяти, потому что локальность резко смещается после просмотра. По мере работы метода порции данных уменьшаются, и в некоторый момент времени будут помещаться в имеющейся памяти. Чем больше пространство памяти, тем скорее порции будут целиком помещаться в физической памяти и тем меньше будут расходы, связанные с листанием. [14]

Быстрая сортировка выбирает элемент списка, называемый осевым, а затем переупорядочивает список таким образом, что все элементы, меньшие осевого, оказываются перед ним, а большие элементы - за ним. В каждой из частей списка элементы не упорядочиваются. Если г - окончательное положение осевого элемента, то нам известно лишь, что все значения в позициях с первой по г - 1 меньше осевого, а значения с номерами от г 1 до N больше осевого. Затем алгоритм Quicksort вызывается рекурсивно на каждой из двух частей. При вызове процедуры Quicksort на списке, состоящем из одного элемента, он ничего не делает, поскольку одноэлементный список уже отсортирован. [15]

Страницы: 1 2 3 4