birlashtirish orqali tartiblash

DOC 9 sahifa 104,0 KB Bepul yuklash

9 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 104,0 KB

Fayl turi DOC

Sahifalar 9

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 9

ma’ruza 12. birlashtirish orqali tartiblash birlashtirish orqali tartiblash algoritmi oldingi boblarda keltirilgan algoritmlarga qaraganda, hech bo'lmaganda tezlik jihatidan ancha samaralidir. pufakchali tartiblash, kiritish orqali tartiblash va tanlash orqali tartiblash o(n2) vaqtni olsa, birlashtirish orqali tartiblash o(n × logn) vaqtni oladi, bu esa tartiblash jarayonini sezilarli darajada tezlashtiradi. misol uchun, agar n (tartiblash uchun ob'ektlar soni) 10 000 bo'lsa, n2 = 100 000 000, n × logn esa 40 000 teng bo'ladi. bundan tashqari, birlashtirish tartibini amalga oshirish nisbatan oson. kontseptual darajada u quicksort va shellsort algoritmlariga qaraganda oddiyroq. agar ushbu sondagi obyektlarni tartiblash uchun kiritish orqali tartiblash 28 soat talab qilsa, birlashtirish orqali tartiblash 40 sekund vaqt talab qiladi. bundan tashqari, birlashtirish orqali tartiblashni amalga oshirish nisbatan oson. kontseptual darajada u tezkor tartiblash va shell tartiblash algoritmlariga qaraganda oddiyroq. birlashtirish tartiblash algoritmi “bo‘lib tashla va hukmronlik qil” tamoyiliga asoslanadi, ya’ni dastlabki masala ikkita kichik qism masalaga bo‘linadi va har bir …

2 / 9

. c massiv a va b ning barcha elementlarini o’z ichiga olgan va tartibni saqlaydi. dastlab, biz birlashtirish jarayonining o'zini ko'rib chiqamiz, keyin esa tartiblashda qanday ishlatilishini aniqlaymiz. faraz qilamiz, bizda ikkita oldindan tartiblangan massiv bor (bir xil o'lchamda bo'lishi shart emas). aytaylik, a massivida 4 ta element, b massivda 6 ta element bo’lib, massivlar c massiviga birlashtirilsin. c massiv dastlab 10 ta bo'sh katakchadan iborat bo’ladi. ikki massivni birlashtirish: a - birlashtirishdan oldin; b - birlashtirgandan so'ng. rasmda doiralardagi raqamlar elementlarning a va b dan c ga ko'chirilish tartibini ko'rsatadi. 8-bosqichdan keyin b massivida hech qanday element yo'qligi sababli, qo'shimcha taqqoslashlar kerak emas; qolgan barcha elementlar oddiygina a dan c ga ko‘chiriladi. endi ushbu algoritmni a massiv berilganda qanday qo’llashni ko’rib chiqamiz. buning uchun algoritmni biroz o‘zgartiramiz, a massivi yarmidan ikki qismga ajratamiz, ularning har biri mustaqil tartiblaymiz, so’ngra bu qismlarni birlashtirishimiz kerak bo’ladi. va buning uchun bizga qo‘shimcha …

3 / 9

radi. bundan tashqari, hosil bo'lgan 2 elementli massivlarning har bir jufti 4 ta elementdan iborat massivga birlashtiriladi. jarayon butun massiv tartiblashtirilgunga qadar doimiy o'lchamdagi massivlar bilan davom etadi. algoritmning murakkabligini baholash: eng yomon holatdagi murakkabligi: o(nlogn) eng yaxshi holatdagi murakkabligi: o(nlogn) o‘rtacha murakkabligi: o(nlogn) eng yomon holatdagi xotira sarfi: o(n) tezkor tartiblash (quicksort). n ta elementdan iborat kirish massivini tartiblash uchun tezkor tartiblash algoritmining eng yomon xolatdagi murakkabligi o(n2) ga teng. eng yomon holatda juda sekin bo'lishiga qaramay, bu algoritm amalda ko'pincha eng yaxshisidir, chunki u o'rtacha hisobda juda samarali: uning kutilayotgan ishlash vaqti o(nlgn) ni tashkil qiladi va baholashdagi yashiringan doimiy koeffitsientlar juda kichikdir. shuningdek, uning afzalligi shundaki, u joyida tartiblashni amalga oshiradi va virtual xotira muhitida ham yaxshi ishlaydi. tezkor tartiblash algoritmining tavsifi. tezkor tartiblash xuddi birlashtirish orqali tartiblash kabi, “”bo'lib tashla va hukmronlik qil” tamoyilidan foydalanadi. uch bosqichli tartiblash jarayoni quyida tasvirlangan: bo'lish : a[l..r] massivi shunday …

4 / 9

ni qismlarga ajratish. ko‘rib chiqilayotgan tartiblash algoritmining muhim qismi partition funksiyasi bo’lib, u a[l..r] massiv ostisi elementlarining tartibini qo‘shimcha xotirani jalb qilmasdan o‘zgartiradi. bo'lish algoritmi quyidagicha: dastlab, massiv ostisi oxirgi elementi a[r] tayanch element sifatida tanlanadi va u aniq to'g'ri o’ringa joylashtiriladigan element hisoblanadi. keyinchalik, u massivning chap uchidan tayanch element qiymatidan katta element topilgunga qadar qarab chiqiladi, so'ngra massivning o'ng uchidan tayanch element qiymatidan kichik element topilguncha qarab chiqadi. undan keyin to'xtashga olib kelgan shu ikkita element o’rinlari almashtiriladi, chunki ular tayanchga nisbatan o'z joylarida emas. jarayon chap tomonidagi barcha elementlar tayanchdan kichik yoki teng, o'ngdagilari esa tayanchdan katta bo'lguncha davom etadi. bo'linishni yakunlash: jarayonni yakunlash uchun a[r] elementi o'ng tomonning eng chap elementi bilan almashtirilishi kerak. ushbu algoritmni amalga oshirish dasturi: int partition(int [] a, int l, int r) { int i = l - 1, j = r, v = a[r]; int t; for (; ; ) …

5 / 9

larning medianasini tanlash uchta nuqtadan medianani aniqlash deb ataladi. albatta, uchta nuqta bo'yicha medianani aniqlash massivning barcha elementlar orasidan aniqlashdan ancha tezroq. biroq, berilganlar to’g’ri yoki teskari tartibda tartiblangan bo'lsa, u eng katta yoki eng kichik elementni tanlashdan muvaffaqiyatli qochadi. bu eng yomon holatning yuzaga kelish ehtimolini kamaytiradi. ehtimol, ba'zi patologik holatlarda bu sxema ham yomon ishlaydi, ammo oddiy vaziyatda bu sizga tayanch nuqta qiymatini tez va samarali tanlash imkonini beradi va algoritmning o'rtacha bajarilish vaqtini 5-10% ga qisqartiradi tanlangan elementlarni tartiblash mumkin va keyin elementlarning o'rtacha qiymatini a[r-1] bilan almashish va keyin a[l+2 ... r-2] bo'yicha bo'lish algoritmini bajarish mumkin. bu takomillashtirishga uchta nuqta orqali mediana usuli deb ataladi. kichik o'lchamli massiv ostilari. rekursiv dastur kichik o’lchamli massiv ostilari uchun o'zini qayta-qayta chaqiradi. bunga yo'l qo'ymaslik uchun siz kichik o’lchamli massiv ostilari uchun oddiy tartiblash algoritmlaridan birini qo'llashingiz mumkin, masalan, kiritish orqali tartiblashni: if(r-l<=m) insertionsort(a,r-l+1); bu erda m - …

Ko'proq o'qimoqchimisiz?

Barcha 9 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"birlashtirish orqali tartiblash" haqida

ma’ruza 12. birlashtirish orqali tartiblash birlashtirish orqali tartiblash algoritmi oldingi boblarda keltirilgan algoritmlarga qaraganda, hech bo'lmaganda tezlik jihatidan ancha samaralidir. pufakchali tartiblash, kiritish orqali tartiblash va tanlash orqali tartiblash o(n2) vaqtni olsa, birlashtirish orqali tartiblash o(n × logn) vaqtni oladi, bu esa tartiblash jarayonini sezilarli darajada tezlashtiradi. misol uchun, agar n (tartiblash uchun ob'ektlar soni) 10 000 bo'lsa, n2 = 100 000 000, n × logn esa 40 000 teng bo'ladi. bundan tashqari, birlashtirish tartibini amalga oshirish nisbatan oson. kontseptual darajada u quicksort va shellsort algoritmlariga qaraganda oddiyroq. agar ushbu sondagi obyektlarni tartiblash uchun kiritish orqali tartiblash 28 soat talab qilsa, birlashtirish orqa...

Bu fayl DOC formatida 9 sahifadan iborat (104,0 KB). "birlashtirish orqali tartiblash"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: birlashtirish orqali tartiblash DOC 9 sahifa Bepul yuklash Telegram