Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika yo

Algoritm samaradorligi:

Taqqoslashlar soni S= N(N-1)/2=(N²-N)/2

Massiv tartiblanganda o’rinlashtirishlar soni M_min=3(N-1)

Massiv teskari tartiblanganda o’rinlashtirishlar soni M_min=M_minN/2=3N(N-1)/2

Ushbu usul bo’yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o’rinlashtirishlar soni tartibi n2 bo’ladi.

Pufaksimon saralash algoritmi

Ushbu usulning 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 ularning o’rni almashtiriladi Misol : massiv - 4, 3, 7, 2, 1, 6.

1-rasm. Pufaksimon saralash usulida massivelementlarining o’rnini almashtirish

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.