tartiblash algoritmlari
Page preview (5 pages)
Scroll down 👇![ma’ruza 11. tartiblash. tartiblash - bu ro'yxat elementlarini ma'lum bir tartibda [o'sish yoki kamayish bo'yicha] joylashtiradigan algoritmdir. tartiblash natijasi kiruvchi berilganlarning qayta tartiblangan ro'yxati hisoblanadi. tartiblash bu kompyuter ilmida ko'p tadqiqotlarni talab qiladigan algoritmlarning muhim toifalaridan biri hisoblanadi. tartiblash yordamida masala murakkabligini sezilarli darajada kamaytirish mumkin va u ko'pincha berilganlar bazasi va qidiruv algoritmlarida keng qo'llaniladi. tartiblash algoritmlari tasnifi (klassifikatsiyasi) tartiblash algoritmlari odatda quyidagi parametrlar asosida toifalarga ajratiladi. taqqoslash amallari soni bo'yicha bunday holda, tartiblash algoritmlari taqqoslash amallari soniga qarab tasniflanadi va eng yaxshi xolatda o(nlogn) va eng yomon xolatda o(n2) hisoblash murakkabligigi ega bo’ladi. taqqoslashlardan foydalanadigan algoritmlardan tashqari, taqqoslashlarsiz (chiziqli) algoritmlar ham mavjud bo'lib, biz ularni ham muhokama qilamiz. almashtirishlar soni bo'yicha bunday holda, tartiblash algoritmlari tartiblash jarayonida amalga oshirilgan almashtirishlar soni bo'yicha tasniflanadi. tezkor xotiradan foydalanishi bo'yicha ba'zi tartiblash algoritmlari "joyida" bajariladi va ularga vaqtinchalik berilganlarni saqlash uchun kichik hajmdagi o(1) yoki o(logn) joy talab qilinadi, ya'ni kichik …](/media/previews/pages/preview_dVJDVv0.webp "tartiblash algoritmlari - Page 1")
![, agar barcha i va j indekslari uchun a[i] kaliti a[j] kalitiga teng bo‘lsa, hamda dastlabki faylda r[i] yozuvi r[j] yozuvidan oldin bo’lib, tartiblangan ro’yxatda ham r[i] yozuvi r[j] yozuvidan oldin kelsa bunday tartiblash barqaror hisoblanadi. ushbu mezon yozuvlarni kalitlar bo'yicha tartiblash uchun ishlatiladi va bir xil kalitga ega yozuvlar tartiblangan massivda o'z ketma-ketligini saqlab qolishini anglatadi. moslashuvchanlik bo'yicha tartiblash algoritmidan foydalanganda uning murakkabligi dastlabki kiruvchi berilganlarning oldindan tartiblanganligiga (tezkor tartiblash) qarab o'zgarishi, ya'ni kirivchi berilganlarning oldindan tartiblanganligi tartiblashning bajarilish vaqtiga ta'sir qilishi mumkin. buni hisobga oladigan algoritmlar adaptiv algoritmlar deb ataladi. boshqa tasniflash tartiblash algoritmlarining boshqa tasniflash usullari: • ichki tartiblash • tashqi tartiblash ichki tartiblash tartiblashda paytida faqat asosiy xotiradan foydalanadigan tartiblash algoritmlari ichki tartiblash algoritmlari deyiladi. bunday algoritmlar barcha xotiraga yuqori tezlikdagi kirish ruxsatiga ega deb faraz qilinadi. tashqi tartiblash tartiblash paytida lenta yoki disk kabi tashqi xotiradan foydalanadigan tartiblash algoritmlariga tashqi tartiblash algoritmlari deyiladi. tartiblash algoritmlari. …](/media/previews/pages/preview_HoVnW2X.webp "tartiblash algoritmlari - Page 2")
![itmlarga nisbatan yagona muhim afzalligi shundaki, u kirivchi berilganlar roʻyxatining tartiblangan yoki yo’qligini darhol aniqlashi mumkin. amalga oshirilishi: void bubblesort(int[] a) { int tmp; for (int k = a.length - 1; k >= 0; k--) { for (int i = 0; i a[i + 1]) { tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp; } } } algoritm o(n2) murakkablikka ega (hatto eng yaxshi holatda ham). joriy o'tish joyida almashtirishlar bo'lmasa, tartiblashni tugatishga ruxsat berish uchun biz uni bitta qo'shimcha o’zgaruvchi yordamida yaxshilashimiz mumkin. ushbu o'zgartirilgan versiya pufakchali tartiblashning eng yaxshi holatini o(n) ga yaxshilaydi. void bubblesort(int[] a) { int tmp, k; bool swp = true; for (k = a.length - 1; k >= 0 && swp; k--) { swp = false; for (int i = 0; i a[i + 1]) { tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp; …](/media/previews/pages/preview_KyMs9L8.webp "tartiblash algoritmlari - Page 3")
![int n = a.length; for (int i = 0; i = 1 && a[j - 1] > v ) { a[j] = a[j - 1]; j--; } a[j] = v; } } tahlil eng yomon holat tahlili: eng yomon holatda har bir i uchun barcha elementlarini siljitishi kerak a[1],. . . , a [i - 1] (ya'ni a[i] qiymati ularning barchasidan kichik) , bu 𝜭(i - 1) vaqtni oladi. umumiy vaqt quyidagicha hisoblanadi: t(n)=𝜭(1)+𝜭(2)+𝜭(3) . . .+𝜭(n - 1)=𝜭(1+2+3+ n- 1)=𝜭(n(n-1)/2)≈𝜭(n2) o‘rtacha holat tahlili o‘rtacha holatda ichki sikl a[i] ni a[1] . . . , a [i - 1] ning o’rtasiga kiritadi. bu 𝜭(i/2) vaqtni oladi. umumiy vaqt sarfi quyidagiga teng bo’ladi: eng yaxshi holat tahlili eng yaxshi holatda, ro’yxat dastlab tartiblangan holatda bo’lib, ichki siklda hech qanday amal bajarilmaydi, ya'ni, t(n)=𝜭(n). murakkablikni baholash: eng yomon holatdagi murakkabligi: o(n2) eng yaxshi holat murakkabligi: o(n) oʻrtacha murakkabligi: o(n2) eng yomon holatda …](/media/previews/pages/preview_V4TZpxD.webp "tartiblash algoritmlari - Page 4")
About "tartiblash algoritmlari"
ma’ruza 11. tartiblash. tartiblash - bu ro'yxat elementlarini ma'lum bir tartibda [o'sish yoki kamayish bo'yicha] joylashtiradigan algoritmdir. tartiblash natijasi kiruvchi berilganlarning qayta tartiblangan ro'yxati hisoblanadi. tartiblash bu kompyuter ilmida ko'p tadqiqotlarni talab qiladigan algoritmlarning muhim toifalaridan biri hisoblanadi. tartiblash yordamida masala murakkabligini sezilarli darajada kamaytirish mumkin va u ko'pincha berilganlar bazasi va qidiruv algoritmlarida keng qo'llaniladi. tartiblash algoritmlari tasnifi (klassifikatsiyasi) tartiblash algoritmlari odatda quyidagi parametrlar asosida toifalarga ajratiladi. taqqoslash amallari soni bo'yicha bunday holda, tartiblash algoritmlari taqqoslash amallari soniga qarab tasniflanadi va eng yaxshi xolatda o(nlogn) va eng ...
This file contains 10 pages in DOCX format (43.1 KB). To download "tartiblash algoritmlari", click the Telegram button on the left.
DOC
DOC
DOCX
PDF
DOCX
DOCX
DOCX
DOCX
DOCX
DOCX
DOCX
DOCX