Axborotlashtirish texnologiyalari

a_i va a_j elementlarni o’rinlarini almashtirib massivni ikki tomondan ko’rib chiqish jarayonini massiv o’rtasiga kelmaguncha davom ettiramiz. Natijada massiv 2 qismga bo’linadi. Chap qismdagi elementlar x dan katta yoki teng bo’ladilar. O’ng tomondagi elementlar x dan kichik yoki teng bo’ladi.
Dastur tuzayotganda bu jarayonni prosedura yordamida amalga oshirish mumkin. Prosedurani rekursiv va norekursiv usullar bilan tuzish mumkin.


Xoara algoritmini rekursiv usulda amalga oshirish
Quyidagi dastur rekursiv prosedurani qo’llaydi.
Prosedure Hoare;
Prosedure sort (L, R: integer);
var i, j: integer; w, x: word;
begin i:=L; j:=R; x:=a[(L+R) div 2];
repeat
while a[i]while a[j]>x do j:=j+1 end;
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 Lif iend {*sort*};
begin sort (1, n);
end {* Hoare*};
Norekursiv dasturni tuzish uchun yordamchi steklardan foydalaniladi.
Algoritmni baholash

Xoara algoritmni unumdorligini tahlil qilamiz. Boshlab bo’linish jarayonini ko’raylik. Qandaydir x ni tanlab biz massivni to’liq o’tamiz. Demak, n ta taqqoslashni amalga oshiramiz. Taqqoslashlarni umumiy soni n*log(n) ekanligi, o’rin almashtirishlar soni esa ekanligi isbotlangan.

Bizning misolimizda x - o’rtancha element deb tanlangan, lekin Xoara fikri bo’yicha X ixtiyoriy tanlanishi kerak. Xoara algoritmning o’rtacha ishlash vaqti teng.


Takrorlash ucun nazorat savollari


1. Tartiblash masalalarining qaysi turlarini bilasiz?
2. Xoaraning tartiblash algoritmi mazmuni nimada?
3. Xoara algoritmini qanday usullar bilan amalga oshirish mimkin?
4. Xoara algoritm bahosini tavsiflab bering.