|
Taqqoslanma saralashlarning bajarilish vaqtlari. Qo‘yish usuli
|
| bet | 5/8 | | Sana | 14.05.2024 | | Hajmi | 37,56 Kb. | | #233609 |
Bog'liq Mirzo Ulug’bek nomidagi O’zbekiston Milliy universiteti Jizzax f-www.hozir.orgTaqqoslanma saralashlarning bajarilish vaqtlari. Qo‘yish usuli. Agar ichki siklga qarasak yozuvlarning tartiblangan qismiga qo‘shilgan element qolgan elementlardan kichik bo‘lsa operasiyalar eng ko‘p bajariladi. Bu holda location o‘zgaruvchisi 0 ga teng bo‘lganda sikl o‘z ishini tugatadi. SHuning uchun yangi element massiv boshiga qo‘shilganda algoritm eng ko‘p bajariladi. Bunday holat joriy massivning elementlari kamayish tartibida joylashgan bo‘lsa bo‘lishi mumkin. Bu yomon holatlardan biridir.
Bunday massivni qayta ishlash jarayoni qanday bo‘lishini ko‘rib chiqamiz. Birinchi massivning ikkinchi elementi qo‘yiladi. U faqat bitta element bilan solishtiriladi. Ikkinchi qo‘yiladigan element (tartib buyicha uchinchi) oldingi ikkita element bilan, uchinchi qo‘yilgan element oldingi uchta element bilan solishtiriladi. Umuman olganda i - qo‘yiladigan element oldingi i ta element bilan solishtiriladi va bu jarayon N-1 marta takrorlanadi. SHunday qilib, qo‘yish usulida tartiblashning qiyinligi yomon holatda quyidagicha bo‘ladi.
O‘rta holatni ikkita etapga bo‘lamiz. Avval navbatdagi elementning joyini aniqlash uchun kerak bo‘ladigan tenglashtirishlarning o‘rtacha sonini hisoblaymiz. Keyin birinchi qadamdan foydalanib barcha kerakli operasiyalarning o‘rtacha sonini hisoblaymiz. i elementning joyini aniqlash uchun kerak bo‘ladigan tenglashtirishlarning o‘rtacha sonini hisoblashdan boshlaymiz. Avval aytib o‘tilganidek, i - elementning massivga qo‘shilishi kerakli joyda turgan bo‘lsa ham kamida bir marta tenglashtirishlarni talab qiladi. Tengliklar quyidagilarni beradi.
Almashtirish usuli tahlili. Biz almashtirish usuli algoritmining qisqacha tahlilini ko‘rib chiqamiz. Qaysi holatda bajariladigan ishning hajmi minimal darajada bo‘ladi. For siklining birinchi aylanishida to‘liq bajarilishi kerak, shuning uchun algoritmda kamida N-1 ta tenglashtirish ko‘rib chiqiladi.
Yaxshi holatda N-1 ta tenglashtirishlar bajariladi. Bu degani massivdagi elementlar to‘g‘ri tartibda joylashgan. Massiv elementlari teskari tartibda joylashgan bo‘lsa, tenglashtirishlar necha marta bajariladi. Birinchi aylanishda N-1 ta, ikkinchi aylanishda N-2 ta tenglashtirishlar bajariladi. Keyingi jarayonlar shuni ko‘rsatadiki, navbatdagi har bir aylanishda tenglashtirishlar soni birga kamayib boradi. SHuning uchun bu holatda qiyinlik quyidagi formula bilan hisoblanadi.
SHell usuli. Tartiblash algoritmlarini tahlil qilishda ayrim hollarda inversiya miqdorini hisoblaymiz. Inversiya – bu noto‘g‘ri tartibda keladigan massivning ikkita elementi. Masalan, (3,2,4,1) massivda 4 ta inversiya mavjud, ular (3,4), (3,1), (2,1), (4,1). Massiv elementlari teskari tartibda joylashgan bo‘lsa, inversiya eng ko‘p bo‘ladi, uning soni (N2-N)/2.
|
| |
