Саралаш алгоритмларини тадқиқ қилиш - Режа:
- Саралаш тушунчаси ва вазифаси;
- Саралаш усулларининг классификацияси;
- Саралаш масаласининг формал қўйилиши;
- Саралашнинг қатъий усуллари:
- қўйиш орқали саралаш;
- танлаш орқали саралаш;
- алмаштириш орқали саралаш.
- 12-Мавзу: Саралашнинг қатъий усуллари
Саралаш тушунчаси ва унинг вазифаси - Саралашдан мақсад - тартибланган тўпламда керакли элементни топишни осонлаштиришдан иборат.
- Саралаш – бу берилган тўплам элементларини бирор бир тартибда (ўсиш ёки камайиш) жойлаштириш жараёнидир.
- дастурларни трансляция қилишда;
- маълумотлар мажмуасини ташқи хотирада ташкил қилишда;
- кутубхоналар, каталоглар, маълумотлар базасини яратишда ва бошқ.
- Маълумотларни хажми ва тузилишига нисбатан саралаш усуллари иккига ажралади, яъни ички ва ташқи:
- ички саралаш – бу оператив хотирадаги саралаш;
- ташқи саралаш – ташқи хотирада саралаш.
- Саралаш масаласини формал қўйилиши
- Берилган: а1, а2 ,…, аn, объектлар тўплами.
- Талаб қилинади: Берилган объектларни тартиблаш, уларни шундай аp1, аp2 ,…, аpn кетма-кетликда ўринлаштириш лозимки, бунда уларнинг калитлари камаймайдиган тартибда жойлашсин: kp1 kp2 … kpn.
- Саралаш алгоритми турғун дейилади, агарда саралаш натижасида бир ҳил калитли объектлар бир-бирига нисбатан ўринларини ўзгартирмаса.
- саралашга кетган вақт (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-Мавзу бўйича назорат саволлари - Саралаш деганда нима тушинилади?
- Саралашнинг вазифаси нимадан иборат?
- Саралашнинг мақсади нимадан иборат?
- Қўйиш орқали саралашнинг ғоясини тушунтириб беринг?
- Танлаш орқали саралаш тушунчаси?
- Пуфаксимон саралаш нима?
Do'stlaringiz bilan baham: |