Saralash usullari mavzusi bo’yicha ma’ruza matni

Saralashning murakkab usullari

Almashtirish bilan(Xoor)	60	116	1
Tanlash bilan (ikkili daraxt yordamida	110	241	1.7
Joylashtirish bilan (Shell)	127	349	2.1

Jabvalda keltirilgan berilganlar xususan, elementlari 512 dan katta bo’lmagan massivlarga nisbatan kerak.
Oddiy saralashlardan (almashtirish bilan saralash) o’nimdorligi bo’yicha eng yomoni Xoor tez satalash usulidan 35 marta sekin ishlaydi.
Oddiy saralashlardan eng tezkori (oddiy joylashtirish bilan saralash), murakkab saralashlardan o’nimdorligi boyicha eng yomonidan (Shell saralashdan) 4,2 marta sekin ishlaydi. Ko’rsatib o’tilgan samaradorliklar massivning o’lchami kattalashgan sari yo’qori darajada namoyish etiladi.

2.1.7. Oddiy joylashtirish bilan saralash va ko’piksimon saralash usulini nazariy taqqoslash

Qaralayotgan bitiruv ishimizdagi saralash algoritmlarini taqqoslashni tavsiya etilgan adabiyotlar asosida bajaramiz. Saralashlarni taqqoslashlarning asosiy kriteriyasi uning samaradorligi ya'niy, uzatishlar soni va taqqoslashlar soni bo'ladi. Berilgan ko’rsatkichlar saralashning vaqtiga ta’sir qiladi.
Berilgan saralashning samaradorligini hisoblash uchun foydalanuvchi asosiy formulani ko’rsatamiz:
− i – “elash”da kalit elementlarining taqqoslashlar soni
− kalitlarni taqqoslashning minimal soni;
− kalitlarni taqqoslashning maksimal soni;
− kalitlarni taqqoslashning o’rtacha soni;
− i – “elash”da kalit elementlarining uzatishlar soni;
− uzatishlarning minimal soni;
− uzatishlarning maksimal soni;
− uzatishlarning ortacha soni;
− massiv o’lchami;
Saralashning oddiy joylashtirish usulini qaraymiz:






Saralashning ko’piksimon usulini qaraymiz:


Berilganlarning metodik formulalari asosida oddiy joylashtirish va ko’piksimon saralash usuli uchun taqqoslash jadbalini tuzamiz:
2-jadval. Oddiy joylashtirish va ko’piksimon saralashning taqqoslash tahlili

Massiv o’lchami