Mavzu: Saralash turlari va algoritmlar samaradorligi. Yaxshilangan usullar

1903-1957 yillar
Ish joylari:
Prinstonski universitet
Berlin universiteti
AQSH atom kommitsiyasi

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

Саралашдан мақсад - тартибланган тўпламда керакли элементни топишни осонлаштиришдан иборат.

Изоҳ
Саралаш – бу берилган тўплам элементларини бирор бир тартибда (ўсиш ёки камайиш) жойлаштириш жараёнидир.

• дастурларни трансляция қилишда;
• маълумотлар мажмуасини ташқи хотирада ташкил қилишда;
• кутубхоналар, каталоглар, маълумотлар базасини яратишда ва бошқ.

Саралашнинг тадбиқи:
Маълумотларни хажми ва тузилишига нисбатан саралаш усуллари иккига ажралади, яъни ички ва ташқи:

• ички саралаш – бу оператив хотирадаги саралаш;
• ташқи саралаш – ташқи хотирада саралаш.

Саралаш масаласини формал қўйилиши
Берилган: а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) – идеал ҳолатда.
Ички саралаш усуллари
Қатъий усуллар
Яхшиланган усуллар

Saralash masalasining qo’yilishi

• N ta elementni tartiblash kerak bo’lsin: ,…. a,b,c, uchta kalit uchun Kalitlar to’plami qandaydir “<” (“>”) tartib bo’yicha saralash amal qilsin: uholda ushbu uchta kalit quyidagi shartlar bajarilsa:
• Trixotomi: a>b yoki ayoki a=b;
• Tranzitivlik: agar a>b va b>c, u holda a>c;

•