Анализ HeapsortНа первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. Процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n Heapsort очень эффективна; чем больше n, тем лучше она работает. В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log2(n/2), log2(n/2-1),...,log2(n-1) позиций (логарифм "обрубается" до следующего меньшего целого). Следовательно, фаза сортировки требует n-1 сдвигов с самое большое log2(n-1), log2(n-2),...,1 перемещениями. Кроме того, нужно еще n-1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heapsort потребует n*log2n шагов. Сортировка с помошью разделения.Теперь коснемся третьего улучшенного метода, основанного на обмене. Улучшение метода, основанного на обмене, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Изобретатель Ч.Хоар назвал этот метод быстрой сортировкой (Quicksort). В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент ai>x, затем будем просматривать массив справа, пока не встретим aj<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую с ключами больше (или равными) x. Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей 44 55 12 42 94 06 18 67 для разделения понадобятся два обмена: 18≈44 и 6≈55. Получаем 18 06 12 42 94 55 44 67 последние значения индексов таковы: i=5, а j=3. Ключи a1...ai-1 меньше или равны ключу x=42, а ключи aj+1...an больше или равны x. Следовательно, существует две части, а именно Ak:1<= k < i:ak <= x Ak: j< k <= n:x <= ak Наша цель - не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям частей, и так до тех пор пока каждая из частей не будет состоять из одного-единственного элемента. Суть итеративного решения заключается во введении списка требуемых разделений, т.е. разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним, и наоборот. В приводимой не рекурсивной версии Quicksort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Вводим индекс s, указывающий на самую последнюю строку в стеке. О том, как выбрать подходящий размер стека m, речь пойдет при анализе Quicksort. const m=4; n=20; type stack=record t,r:integer; end; type mass=array[1..n] of integer; var i,j,t,r,x,w:integer; s: 0..m; a: mass; st: array[1..m] of stack; Begin writeln; QuicksortДля исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений x ожидаемое число операций обмена равно числу элементов в левой части разделяемой последовательности, т.е. n-1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна (n-(x-1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x. m = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n = [Su: 1<= x <= n-1:u*(n-u)]/n2 = [n*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 Представим себе, что нам всегда удается выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего log2n проходов. В результате общее число сравнений равно n*log2n, а общее число обменов - n*log2(n)/6. Средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффициентом 2*ln(2). Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них - недостаточно высокая производительность при небольших n. |