Saralash usullari mavzusi bo’yicha ma’ruza matni

Oddiy joylashtirish usuli
Ko’piksimon usuli
Kalitlarni taqqoslash soni (o’rta qiymati)	Uzatishlar soni (o’rta qiymati)	Kalitlarni taqqoslash soni (o’rta qiymati)	Uzatishlar soni (o’rta qiymati)
32	263	329	256	384
64	1039	1163	1024	1536
128	4127	4379	4096	6144
256	16447	16953	16384	24576
512	65663	131835	65536	98304
1024	262399	264443	262144	393216

2-jadvalda olingan qiymatlar asosida ikki saralash usuli bo’yicha kalitlarni taqqoslash soni va uzatishlar soni uchun taqqoslashlar grafigini tuzamiz”:

10-rasm. Kalitlarni taqqoslash sonlari grafigi: kalitlarni taqqoslar soni (ko’piksimon) – ko’piksimon usuli uchun, kalitlarni taqqoslashlar soni (joylashtirish) – oddiy joylashtirish usuli uchun
Olingan grafiklar asosida joylashtirish usulidagi saralashga nisbatan ko’piksimon usulida saralashda kalitlar soni katta ekanligini aytish mumkin. Shunday qilib, berilgan kriteriya bo’yica saralashning ko’piksimon usuliga qaraganda oddiy joylashtirish usulining samaradorligi nisbatan yuqori.
Olingan grafikga asoslanib massiv o’lchamining kichik qiymatlarida ikki usul uchun ham uzatishlar soni taxminan bir xil ekanligini aytish mumkin. Katta o’lchamdagi (512 dan katta) massivlarda oddiy joylashtirish usuliga nisbatan ko’piksimon usulida uzatishlar soni tezroq ortadi. Shunday qilib, berilgan xususiyatlar bo’yicha joylashtirish usuli samaradorligi yuqori. 1-jadvalda nazarda tutilayotgan joylashtirish usulidagi saralashdan ko’ra ko’piksimon usulida saralashga ko’p vaqt talab etilishini ta’kidlash mumkin. Bundan, umuman olganda oddiy joylashtirish usulida saralash ko’piksimon usulida saralashdan ko’ra samaraliroq ekanligi kelib chiqadi.



11-rasm. Saralashlardagi uzatishlar soni grafigi: K - uzatishlar soni – ko’piksimin usuli uchun, J - uzatishlar soni – oddiy joylashtirish usuli uchun.