tartiblash

DOC 11 pages 103.0 KB Free download

11 pages

FaylHub.uz

Download via Telegram

Size 103.0 KB

File type DOC

Pages 11

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 11

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 …

2 / 11

, 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. …

3 / 11

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; …

4 / 11

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 …

5 / 11

deyarli chiziqli hisoblanadi; • tanlash orqali tartiblash kattaroq qiymatlar va kichik kalitlarga ega elementlar uchun eng mos keladi. shell tartiblash shell tartiblash (shuningdek, asta kamayib boruvchi tartiblash deb ham aytiladi) donald shell tomonidan ixtiro qilingan. bu tartiblash kiritish orqali tartiblashning umumlashmasidir. kiritish orqali tartiblash qisman tartiblangan kiruvchi berilganlarda samarali ishlaydi. shell tartiblash, shuningdek, n-oraliqli kiritish ortali tartiblash sifatida ham tanilgan. kiritish orqali tartiblashda faqat qo'shni elementlar juftliklarini solishtiradi, shell tartiblashda bir nechta o'tishlarni amalga oshiradi va har bir o'tishda solishtiriladigan elementlar o’rtasidagi oraliq turlicha bo’ladi. kiritish orqali tartiblash qo'shni elementlarni taqqoslaydi va n ta siljish amalini bajaradi. shell tartiblashda qo'llaniladigan variant quyidagicha: qo'shni taqqoslash algoritmning oxirgi bosqichida amalga oshiriladi, shuning uchun shell tartiblashning oxirgi bosqichi aslida kiritish orqali tartiblash algoritmidir. bu bir-biridan uzoqda joylashgan elementlarni solishtirish va almashish imkonini berib, kiritish orqali tartiblashni yaxshilaydi. bu solishtirish orqali tartiblash algoritmlari orasida kvadratik vaqtdan kamroq vaqt ichida bajariladigan birinchi algoritmdir. shell sort …

Want to read more?

Download all 11 pages for free via Telegram.

Download full file

About "tartiblash"

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 11 pages in DOC format (103.0 KB). To download "tartiblash", click the Telegram button on the left.

Tags: tartiblash DOC 11 pages Free download Telegram