Адабиётлар

Саралаш масаласини қўйилишини қуйидагича ёзиш мумкин. 
Фараз қилайлик, а
1
, а
2 
,…, а
n
, элементлар кетма-кетлиги берилган 
бўлсин. У ҳолда саралаш алгоритми элементларни массивга шундай 
жойлаштирадики, натижада улар қандайдир муносабатга нисбатан 
f(а
к1
) f(а
к2
) … f(а
кn
) тартибга эга бўлади. Одатда f тартиблаш функцияси 
қандайдир махсус қоида билан ҳисобланмасдан, балки элементни калит 
қиймати бўйича массив элементлари тартибланади.
Маълумотларга қайта ишлов берилаѐтганда маълумотни информацион 
майдонини ҳамда уни машинда жойлашишини (адресини) билиш зарур. 
Саралашни иккита тури мавжуд: ички ва ташқи: 
ички саралаш бу оператив хотирадаги саралаш; 
ташқи саралаш – ташқи хотирада саралаш. 
Саралаш бу маълумотларни калитлари бўйича хотирада регуляр 
кўринишда жойлаштиришдир. Регулярлик деганда маълумотлар калит 
қийматлари бўйича массивда бошидан охиригача ўсиши ѐки камайиши 
тушинилади. 

---

―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев 
Агар сараланаѐтган ѐзувлар хотирада катта хажмни эгалласа, у ҳолда 
уларни алмаштиришлар катта сарф (вақт ва хотира маъносида) талаб қилади. 
Ушбу сарфни камайтиши мақсадида, саралаш калитлар адреси жадвалида 
амалга 
оширилади. 
Бунда 
фақатгина 
маълумот 
кўрсаткичлари 
алмаштирилиб, массив ўз жойида қолади. Юқоридаги усул адреслар 
жадвалини саралаш усули дейилади. 
Сараланаѐтганда бир ҳил калитлар учраши мумкин, бу ҳолда 
сараланагандан кейин бир ҳил калитлилар бошланғич тартибда қандай 
жойлашган бўлса, ушбу тартибда қолдирилиши мақсадга мувофиқ бўлади 
(Бир ҳил калитлилар ўзларига нисбатан). Бундай усулга турғун саралаш 
дейилади. 
Саралаш самарадорлигини бир неча мезонлар бўйича баҳолаш мумкин: 
саралашга кетган вақт; 
саралаш учун талаб қилинган оператив хотира; 
дастурни ишлаб чиқишга кетган вақт. 
Биринчи 
мезонни 
қараб 
чиқайлик. 
Саралаш 
бажарилганда 
таққослашлар ѐки алмаштиришлар сони ҳисоблаш мумкин. 
Фараз қилайлик, Н = 0,01n
2
+ 10n – таққослашлар сони. Агар n < 1000 
бўлса, у ҳолда иккинчи қўшилувчи катта, акс ҳолда яъни, n > 1000 бўлса, 
биринчи қўшилувчи катта бўлади. 
Демак, кичкина n ларда таққослашлар сони n га тенг бўлади, катта n 
ларда эса n
2
га тенг бўлади. 
Саралашда таққослашлар сони қуйидаги оралиқларда бўлади: 
0(n log n) дан 0 (n
2
) гача; 0 (n) – идеал ҳолатда. 
Саралашни қуйидагича усуллари бор: 
қатъий (тўғридан-тўғри) усуллар; 
яхшиланган усуллар. 
Қатъий усуллар: 
1. тўғридан-тўғри қўшиш усули;
2. тўғридан-тўғри танлаш усули;
3. тўғридан-тўғри алмаштириш усули. 
Юқорида келтирилган учала усулда ҳам алмаштиришлар сони деярли 
бир ҳил бўлади.