“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Саралашнинг тадбиқи:

Саралаш усулларининг классификацияси

• Маълумотларни хажми ва тузилишига нисбатан саралаш усуллари иккига ажралади, яъни ички ва ташқи:
• ички саралаш – бу оператив хотирадаги саралаш;
• ташқи саралаш – ташқи хотирада саралаш.
• Саралашнинг қатъий усуллари;
• Саралашнинг яхшиланган усуллари.

Саралаш масаласини формал қўйилиши
Берилган: а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 бўлган объектлар берилган бўлсин.
- бошланғич ҳолат
Қўйиш орқали саралаш алгоритми таҳлили
Энг ёмон, яъни бошланғич объектлар калит қийматлари бўйича камайиш тартибида берилган ҳолат.