Mavzu: Saralash turlari va algoritmlar samaradorligi. Yaxshilangan usullar

Qaysi saralash algoritmi samarali?

• Ularning deyarli hammasi ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi.
• Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.

Pufakli saralash algoritmi

• Pufakli saralash algoritmini uch punktda ifodalsh mumkin:
• 1) butun massiv bo’ylab o’tish;
• 2) ikkita qo’shni yachekalarni o’zaro solishtirish;
• 3) agar i yachekadagi element i+1 yecheykadagi elementdan katta bo’lsa, u holda bu elementlar o’rni almashadi.

Ishchi algoritmi qanday tashkil etiladi?

• Massivning hamma elementidan N marta to’liq o’tish uchun Ikkita for sikli yaratiladi;
• if operatori yordamida ikkita qo’shni yacheykalar taqqoslanadi;
• Shart bajarilsa o’rni almastiriladi;

Pufakli saralash algoritmiga oid dastur kodi quyidagicha:

Yutuqi: oson qo’llash mumkin;

• Yutuqi: oson qo’llash mumkin;
• Kamchiligi: saralash juda sekin amalga oshiriladi.

Bu algoritmni takomillashtirish mumkin.

Қўйиш орқали саралаш
Алгоритм ғояси
Объектлар ҳаёлан “тайёр” a(1),...,a(i-1) ва бошланғич кетма-кетликларга бўлинади. Ҳар бир қадамда (i=2 дан бошлаб) бошланғич кетма-кетликдан i-чи элемент ажратиб олиниб тайёр кетма-кетликнинг керакли жойига қўшилади.
Мисол: Фараз қилайлик, калит қийматлари 40,51,8,38,90,14,2,63 бўлган объектлар берилган бўлсин.
- бошланғич ҳолат
Қўйиш орқали саралаш алгоритми таҳлили
Энг ёмон, яъни бошланғич объектлар калит қийматлари бўйича камайиш тартибида берилган ҳолат.
Таққослашлар сони: