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 L

if i

end {*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.
Mustaqil ishlash uchun nazorat savollari:

1. 
   Algoritmni baholash uchun qo’llanishi mumkin bo’lgan mezonlarni tavsiflab bering.
   
2. 
   Turli mezonlar bo’yicha baholash jarayoniga misollar ko’rsating.
   
3. 
   Tartiblash usllariga 5 ta misol ko’rsating.
   
4. 
   Xoara tartiblash algoritmi yordamida yechiladigan masalalar turkumini tasniflab bering
   
5. 
   Xoara tartiblash algoritmini rekursiv bo’lmagan dasturini tuzing.
   
6. 
   Xoara tartiblash algoritmini ob’yektli yo’naltirilgan dasturlash tilida amalgam oshiring.