Rambler's Top100

Анализ 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  
   for i:=1 to n do  
     begin  
       a[i]:=random(100); write(a[i],'  ');  
     end;  
   s:=1; st[s].t:=1; st[s].r:=n;  
   repeat  {выбор из стека последнего запроса}  
     t:=st[s].t;r:=st[s].r;s:=s-1;  
       repeat  {разделение a[t]...a[r]}  
         i:=t;j:=r;x:=a[(l+r) div 2];  
         repeat  
           while a[i]<x do i:=i+1;  
           while x<a[j] do j:=j-1;  
           if i<=j then  
                   begin  w:=a[i];a[i]:=a[j];a[j]:=w;  
                          i:=i+1;j:=j-1; end;  
         until i>j;  
         if i<r then   {запись в стек запроса из правой части}  
                begin s:=s+1; st[s].t:=i;st[s].r:=r; end;  
         r:=j;  {теперь t и r ограничивают левую часть}  
       until t>=r;  
   until s=0;  

   writeln;  
   for i:=1 to n do  
     write(a[i],'  ');  
End.  

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.  

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz