“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш



Download 1,48 Mb.
Sana22.02.2022
Hajmi1,48 Mb.
#100750
Bog'liq
MTA 12 new full

Саралаш алгоритмларини тадқиқ қилиш

  • Режа:
  • Саралаш тушунчаси ва вазифаси;
  • Саралаш усулларининг классификацияси;
  • Саралаш масаласининг формал қўйилиши;
  • Саралашнинг қатъий усуллари:
    • қўйиш орқали саралаш;
    • танлаш орқали саралаш;
    • алмаштириш орқали саралаш.

Саралаш тушунчаси ва унинг вазифаси

  • Саралашдан мақсад - тартибланган тўпламда керакли элементни топишни осонлаштиришдан иборат.
  • Изоҳ
  • Саралашбу берилган тўплам элементларини бирор бир тартибда (ўсиш ёки камайиш) жойлаштириш жараёнидир.
  • дастурларни трансляция қилишда;
  • маълумотлар мажмуасини ташқи хотирада ташкил қилишда;
  • кутубхоналар, каталоглар, маълумотлар базасини яратишда ва бошқ.
  • Саралашнинг тадбиқи:
  • Маълумотларни хажми ва тузилишига нисбатан саралаш усуллари иккига ажралади, яъни ички ва ташқи:
  • Саралаш масаласини формал қўйилиши
  • Берилган: а1, а2 ,…, аn, объектлар тўплами.
  • Талаб қилинади: Берилган объектларни тартиблаш, уларни шундай аp1, аp2 ,…, аpn кетма-кетликда ўринлаштириш лозимки, бунда уларнинг калитлари камаймайдиган тартибда жойлашсин: kp1  kp2  …  kpn.
  • Def.
  • Саралаш алгоритми турғун дейилади, агарда саралаш натижасида бир ҳил калитли объектлар бир-бирига нисбатан ўринларини ўзгартирмаса.
  • саралашга кетган вақт (T(n)=C(n)+M(n), бунда C(n) - таққослашлар сони; M(n) - эса ўринлаштиришлар сони);
  • дастурни ишлаб чиқишга кетган вақт;
  • талаб қилинадиган хотира хажми.
  • Саралашга кетган вақт учун қуйидаги ўринли бўлади:
  • O(nlogn)  T(n)  O(n2);
  • T(n)=O(n) – идеал ҳолатда.
  • Ички саралаш усуллари
  • Қатъий усуллар
  • Яхшиланган усуллар

Саралашнинг қатъий усуллари

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

Шелл саралаши (қисқариб борувчи қадамлар орқали саралаш)

  • Шелл саралаши (қисқариб борувчи қадамлар орқали саралаш)
  • Бошида бир биридан 4 қадамда жойлашган элементлар ўзаро гуруҳланиб саралаш амалга оширилади. Бундай жараён тўртлик саралаш деб аталади. Биринчи ўтишдан кейин элементлар қайта гуруҳланиб, энди ҳар икки қадамдаги элементлар таққосланади. Бу эса иккилик саралаш деб номланади. Ва ниҳоят, учинчи ўтишда оддий ёки яккалик саралаши амалга оширилади.

12-Мавзу бўйича назорат саволлари

  • Саралаш деганда нима тушинилади?
  • Саралашнинг вазифаси нимадан иборат?
  • Саралашнинг мақсади нимадан иборат?
  • Қўйиш орқали саралашнинг ғоясини тушунтириб беринг?
  • Танлаш орқали саралаш тушунчаси?
  • Пуфаксимон саралаш нима?

Download 1,48 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish