Пирамидално сортиране

Методът за сортиране чрез пряка селекция се базира на последователното избиране на най-малкото измежду на n-те елемента на масива, след това измежду на (n-1) елемента на масива и т.н. Ясно е, че намирането на най-малкия елемент измежду n елемента изисква n-1 сравнения, а за намирането му измежду n-1 елемента - n-2 сравнения. Как може това сортиране чрез селекция да се подобри? Това може да стане, като при всяко сканиране се запазва повече информация, а не само идентификацията на най-малкия елемент. Например с n/2 сравнения може да се определи по-малкият елемент за всяка двойка от елементи, с други n/4 сравнения – двойката, която съдържа най-малкия елемент измежду две двойки и т.н. Най-после само с n-1 сравнения може да се построи дърво на селекциите, както е показано на фиг.1, коренът на което ще бъде търсеният най-малък елемент.

Втората стъпка се състои в слизане по пътя, маркиран от най-малкият елемент, и последователното му заместване или с празна дупка на дъното, или с елемента на алтернативния клон при междинните възли. (фиг. 2 и фиг. 3). Отново елементът, който се е появил в корена на дървото, има най-малка стойност (този път втори по ред) и може да се елиминира. След n такива стъпки на селекция дървото се изпразва (т.е. напълва се с дупки) и процесът на сортиране завършва. Трябва да се отбележи, че всяка една от n-те стъпки на селекция изисква само log₂ n сравнявания. Следователно пълният процес на селекция изисква от порядъка на nlog₂ n елементарни операции освен n-те стъпки, необходими за построяване на дървовидната структура. Това е много съществено подобрение по отношение на преките методи, които изискват n² стъпки и дори в сравнение със сортирането по Шел, което изисква n^1*2 стъпки.

Естествено тук трябва да се държи сметка за много повече неща и затова сложността на отделните стъпки в метода на сортиране чрез дърво е по-голяма; за да се запази увеличеното количество информация, натрупана от началното преминаване, трябва да се създаде определен вид дървовидна структура. Нашата следваща задача е да намерим методи за ефикасно организиране на информацията.

Естествено би било твърде желателно да се елиминира необходимостта от дупките, които накрая покриват цялото дърво и са източник на много нежелани сравнения. Освен това трябва да се намери начин за представяне на дърво с n елемента в n единици от паметта, а не в 2n-1, както е показано по-горе. Тези цели се достигат чрез метода, наречен пирамидално сортиране с автор J. Williams. Ясно е, че този метод представлява сериозно подобрение на повечето общоприети методи за сортиране чрез дърво.

Пирамида се нарича редица от ключове h_l, h₁₊₁,……h_r,

за която е изпълнено условието:

h_i≤ h_2i

h_i ≤ h_2i+1

за всяко i = l … n/2.

Ако двоичното дърво се представи като масив, както е показано на фиг. 4, следва че дърветата при сортирането на фиг. 5 и фиг. 6 са пирамиди и в частност, че елементът h1 на една пирамида е нейният най-малък елемент.

Нека сега разгледаме следният случай: за някакви стойности l и r е дадена пирамида с елементи h_l+1,…….,h_r. Трябва да добавим нов елемент х, за да получим разширената пирамида h_l,……h_r. Да вземем например за начална пирамиада показаната на фиг. 5 и да я разширим “отляво” е елемента h_l=44.

Новата пирамида се получава като х се постави на върха на дървото и след това се "отсее" по пътя на по-малките елементи, които в същото време се предвижват нагоре. В даденият пример стойността 44 най-напред се разменя с 6, а след това – с 12 и така се получава дървото на фиг. 6.

Елегантен начин за построяване на пирамида на място (в рамките на същия масив) е предложил R.W.Floyd. Той изхожда със следните постановки:

1) ако е даден масив a[n], може да се каже, че елементите от a[n/2] до a[n-1] образуват пирамида, т.к. никой от двата индекса i и j не е изпълнено уравнението

j=2i

или

j=2i+1,

т.е. няма конфликт с дефиницията за пирамида;

2) пирамидата се разширява отляво, като на всяка стъпка се добавя по един елемент от масива. Този процес е показан на фиг.7.

44 55 12 42 94 18 6 67

44 55 12 42 94 18 6 67

44 55 6 42 94 18 12 67

44 42 6 55 94 18 12 67

44 42 6 55 94 18 12 67

6 42 44 55 94 18 12 67

6 42 12 55 94 18 44 67

Елемента със стойност 6 е “изплувал” най-отпред в масива, т.е. на върха на пирамидата. Той трябва да бъде отнет и заместен с безкрайност. Но в програмирането няма стойност безкрайност, поради което прибягваме до следната хитрост: вземаме първият елемент и го разменяме с последния елемент на масива.

6 42 12 55 94 18 44 67

67 42 12 55 94 18 44 | 6

Разглеждаме вече подмасива от първия до предпоследния елемент. При това положение всички елементи с изключение на първия отговарят на условието за пирамида. Трябва да извършим отсяване и за първия елемент.

67 42 12 55 94 18 44 | 6

12 42 67 55 94 18 44 | 6

12 42 18 55 94 67 44 | 6

Вследствие на отсяването и вторият по големина елемент е “изплувал” най-отпред. Правим размяна с последния елемент от подмасива и прилагаме отсяване за новия първи елемент.

12 42 18 55 94 67 44 | 6

44 42 18 55 94 67 | 12 6

18 42 44 55 94 67 | 12 6

И третият по големина елемент е “изплувал” най-отпред. Правим нова размяна с последния елемент от подмасива и прилагаме отсяване за новия първи елемент. И така, докато остане само един елемент в подмасива.

95 | 67 55 44 42 18 12 6

Оказва се, че подмасива е подреден, но в низходящ ред. Какво може да се направи за да подредим масива във възходящ ред? Просто можем да отсяваме най-отпред не най-малкия, а най-големия елемент на масива. Тогава след размяната той ще застане на точното си място. В този случай условието за пирамида се променя по следният начин:

h_i³ h_2i

h_i ³ h_2i+1

Има и едно допълнително условие, което трябва да разгледаме преди да пристъпим към програмната реализация на алгоритъма. В С++ началният индекс на масивите е 0. Горното условие за i=0 би изглеждало така:

h₀³ h_2.0

h_i ³ h_2.0+1

или

h₀³ h₀

h_i ³ h₁

Т.е. първият елемент се сравнява съм със себе си, което вече противоречи на условието за пирамида. Поради тази причина променяме условието за пирамида по следния начин:

h_i³ h_2i+1

h_i ³ h_2i+2

Алгоритъма с който се добавя елемент от ляво на масив, удовлетворяващ условието за пирамидата е описан с функцията shift, където left е началния, а right – крайния индекс на подмасива, за който трябва да се удовлетвори условието за пирамидата. (Добавя се елемент с индекс left, като се счита че всички останали елементи удовлетворяват условието за пирамида.)

void shift(int left, int right)

{

int i, j;

float x;

i = left; //i-индекса на елемента, чието място се търси

j=2*i+1; //j – индекса на първия от елементите-наследници

x=a[i]; //x - запомня стойността на елемента, за който се извършва проверката

while (j<= right) //докато j е в границите на масива

{

if (j< right) //ако съществува индекс j+1 в масива

if (a[j]<a[j+1]) j++; //в j се запомня индекса на > от двата елемента-наследници

if (x>=a[j]) break; //ако х> от по-големия, значи х си е на мястото

a[i]=a[j]; //в противен случай j-тия елемент се записва на мястото на i-тия

//(изкачва се нагоре в пирамидата)

i=j; j=2*i+1; //изчисляват се новия индекс на елемента, чието място се търси

//и индекса на първия новите два наследника в пирамидата

}

a[i]=x; //i е търсеното място за елемента х

}

Ако считаме, че елементите на масива от средата до края отговарят на условието за пирамида, можем последователно да добавим всички елементи отляво, като ги отсеем на подходящото им място посредством функцията sift.

left=(n / 2)+1;

while (left >0)

{

left = left-1; sift (left, n-1);

}

Размяната на първия и последния елемент от неподредения подмасив и последващото намиране на мястото на новия първи елемент в пирамидата може да се опише със следващите оператори.

while (right >0)

{

pom=a[0]; a[0]=a[right]; a[right]=pom; //размяна

right--; //дясната граница на неподредения подмасив намалява с 1

shift (0, right); //отсяване

}

Пълен код на програмата.

# include <iostream.h>

void input(float a[100], int &n)

{ int i;

cout<<"n="; cin>>n;

for(i=0;i<n;i++)

{

cout<<"a["<< i <<"]=";

cin>>a[i];

}

}

void output(float a[100], int n)

{ int i;

for(i=0;i<n;i++)

cout<<"a["<< i <<"]="<<a[i]<<"\n";

}

void shift(float a[100],int left, int right)

{

int i, j;

float x;

i = left;

j=2*i+1; x=a[i];

while (j<= right)

{

if (j< right)

if (a[j]<a[j+1]) j++;

if (x>=a[j]) break;

a[i]=a[j];

i=j; j=2*i+1;

}

a[i]=x;

}

void sort (float a[100], int n)

{

int left, right;

float pom;

left = n/2+1;

right = n-1;

while (left>0)

{

left--;

shift (a,left, right);

}//При напускане на цикъла left=0.

while (right >0)

{

pom=a[left]; a[left]=a[right]; a[right]=pom;

right--; shift (a,left, right);

}

}

void main()

{

int n;

float a[100];

input(a,n);

sort(a,n);

output(a,n);

}

От пръв поглед не се вижда, че този метод на сортиране дава добри резултати. Наистина процедурата не се препоръчва за малък брой елементи, какъвто беше използван в примера. Но за големи n пирамидалното сортиране е много ефикасно и колкото по-голямо е n, толкова е по-добре – дори и по отношение на сортирането по Шел.

В най-лошият случай са необходими n/2 стъпки на отсяване, които отсяват елементите през log (n/2), log (n/2-1),….., log (n-1) позиции, като логаритъмът е с основа 2 и се пресмята с точност до единиците, без да се прави закръгляване. След това фазата за сортиране прави n-1 отсявания с най-много log (n-1), log (n-2),….., 1 движения. Освен това има n-1 движения, за да се струпат отсетите елементи вдясно. Тези сведения показват, че пирамидалното сортиране изисква от порядъка на n * log(n) стъпки дори в най-лошия случай. Тази превъзходна, макар и най-неблагоприятна ефективност е едно от най-силните качества на пирамидалното сортиране.