3-Amaliy mashg’ulot

Algoritm samaradorligi: 

Taqqoslashlar soni M = 

n

n

n

n

2

1

2

2

(

)

 



. 

Almashtirishlar soni C

min

 = 3(n - 1), C

max

 = 3(n - 1)

n

2

   

(n

2

 

tartib).  

Ushbu  usul  bo’yicha  saralash  bajarilsa,  eng  yomon  xolda  taqqoslashlar  va 

almashtirishlar soni tartibi n

2

 bo’ladi. 

 

To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon) 

 

Ushbu usulni g’oyasi  quyidagicha: n  - 1 marta massivda quyidan yuqoriga qarab 

yurib  kalitlar  jufti-jufti  bilan  taqqoslanadi.  Agar  pastki  kalit  qiymati  yuqoridagi  jufti 

kalitidan kichik bo’lsa, u holda ular o’rni almashtiriladi.  

 

Paskal tilidagi dasturi: 

for i := 2 to n do 

  for j := n downto i do 

    if a[j - 1] > a[j] then 

      begin 

        x := a[j - 1]; 

        a[j - 1] := a[j]; 

        a[j] := x; 

      end; 

Bizning xolatda bitta o’tish “bekor” bo’ldi. Elementlarni ortiqcha o’rinlashtirmaslik 

uchun bayroqcha kiritish mumkin. 

Pufaksimon  usulni  yaxshilangan  usuli  bu  sheyker  saralash  usuli  bo’lib,  har  bir 

o’tishdan keyin tsikl ichida yo’nalish o’zgartiriladi.