Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja

F_a (N) - o'rtacha holat bu N o'lchovining aniq muammolarini echish uchun A algoritmi tomonidan bajarilgan operatsiyalarning o'rtacha soni:

F_a(N) = (1 / M_DN)* {F_a (D)} - o'rtacha holat D_N

2. Elementar saralash usullari

Bubble sort eng mashhur saralash algoritmlaridan biridir. Bu erda siz qo'shni elementlarning qiymatlarini ketma-ket taqqoslashingiz va agar oldingisi keyingisidan katta bo'lsa, raqamlarni almashtirishingiz kerak. Shunday qilib, katta qiymatlarga ega elementlar ro'yxatning oxirida, kichikroq qiymatlar esa boshida qoladi.

Ushbu algoritm ta'lim hisoblanadi va unumdorligi pastligi sababli amalda deyarli qo'llanilmaydi: u kichik elementlar (ular "toshbaqalar" deb ataladi) massiv oxirida joylashgan testlarda sekin ishlaydi. Biroq, ko'plab boshqa usullar, masalan, silkituvchi saralash va taroqli saralash kabilarga asoslangan.

3. Tezkor saralash


Tezkor saralash algoritmi(Quick sort).

• 
  Bu algoritm 1964 yilda Charlz Hoar tamonidan taklif qilingan.
  

Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “Tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm.

• 
  Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.
  

Algoritmning g’oyasi:

• 
  Massivda bo’luvchi element X tanlanadi.
  
• 
  Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin.
  
• 
  Natijada chap tamonda barcha kichik elementlar, o’ng tamonda esa barcha katta sonlar joylashib qoladi. Bu qismlarning endi bir-biriga aloqasi yo’q. Keyin ularni alohida saralaymiz.
  

Bu jarayon rekursiv jarayon bo’ladi.

• 
  [L, R] saralanishi kerak bo’lgan kesma.
  
• 
  m = (L+R) / 2 – bu kesmanig o’rtasi.
  
• 
  X=a[m] - bo’luvchi element. Ya’ni uni o’rtasidan tanlab olamiz.
  

Keyin quyidagi amallarni bajaramiz:

• 
  Chap tamondan X dan katta yoki teng bo’lgan birinchi elementni topamiz.
  
• 
  O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.
  
• 
  Ikkalasining qiymatini almashtiramiz.
  

Natijada chap tamondan bitta katta element o’ng tamonga o’tadi, ong tamondan bitta kichik element chapga o’tadi.

1) Bo’luvchi element x=6. Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 10, chap tamondan 6 dan kichik yoki teng bo’lgan element 3.
Ularning o’rnini almashtiramiz.


2) Endi chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 9, chap tamondan 6 dan kichik yoki teng bo’lgan son 2.
Ularning o’rnini almashtiramiz.


3) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 10, chap tamondan 6 dan kichik yoki teng bo’lgan son 1.
Ularning o’rnini almashtiramiz.


4) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 7, chap tamondan 6 dan kichik yoki teng bo’lgan son 6.
Ularning o’rnini almashtiramiz.


Natijada j > i bo’lib qoldi. Bu iteratsiyani shu yerda to’xtatamiz va keyingi bosqichga o’tamiz:

Berilgan interval ikkita qismga ajralib qoldi: [L, j] va [i,R] intervallar. Bu qismlarning bir-biriga aloqasi yo’q, chunki o’ng tamondagi barcha sonlar chap tamondagi barcha sonlardan katta(aniqrog’i kichik emas). Endi bu qismlarni huddi shunday jarayon bo’yicha saralashni davom ettirish mumkin. Buni amalaga oshirish uchun eng yaxshi usul bu rekursiv usuldan foydalanish. [L, R] ni saralash kerak bo’lgan masala undan kichikroq ikkita masalaga [L, j] va [i,R] intervallarni saralashga keltirldi. Bu esa bo’lib tashla va hukmronlik qil metodi deb nomlanadi.
Algoritmning C++ dagi kodini keltiramiz:

•