“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

 

---

34
6-Тажриба иши. МАЪЛУМОТЛАРНИ САРАЛАШ УСУЛЛАРИ 
Ишдан мақсад: Саралаш усулларини тадқиқ қилиш ва ўрганиш. 
Қўйилган масала: саралаш усуллари дастурини Паскал тилида яратиш кўникмасига эга бўлиш. 
Иш тартиби: 
 Тажриба иши тавсифини ўрганиш; 
 Берилган топшириқни дастури алгоритмини ишлаб чиқиш; 
 ПАСКАЛ тилида дастурни яратиш; 
 Дастурни ишлатиш; 
 масалани ечиш; 
 хисоботни тайёрлаш. 
Қисқача назария 
Маълумотларни ЭХМ да қайта ишлашда элементни информацион майдони ва уни машина хотирасида 
жойлашишини билиш зарур. Шу мақсадда маълумотларни саралаш амалга оширилади. Демак, саралаш – бу 
маълумотларни калитлари бўйича доимий кўринишда машина хотирасида жойлаштиришдан иборат. Бу ерда 
доимийлик маълумотларни массивда калитлари бўйича ўсиши тартибида берилиши тушунилади. 
Маълумотларга қайта ишлов берилаётганда маълумотни информацион майдонини ҳамда уни машинда 
жойлашишини (адресини) билиш зарур. 
Саралашни иккита тури мавжуд: ички ва ташқи: 

ички саралаш бу оператив хотирадаги саралаш; 

ташқи саралаш – ташқи хотирада саралаш. 
Агар сараланаётган ёзувлар хотирада катта хажмни эгалласа, у ҳолда уларни алмаштиришлар катта 
сарф (вақт ва хотира маъносида) талаб қилади. Ушбу сарфни камайтиши мақсадида, саралаш калитлар адреси 
жадвалида амалга оширилади. Бунда фақатгина маълумот кўрсаткичлари алмаштирилиб, массив ўз жойида 
қолади. Юқоридаги усул адреслар жадвалини саралаш усули дейилади. 
Сараланаётганда бир ҳил калитлар учраши мумкин, бу ҳолда сараланагандан кейин бир ҳил калитлилар 
бошланғич тартибда қандай жойлашган бўлса, ушбу тартибда қолдирилиши мақсадга мувофиқ бўлади (Бир ҳил 
калитлилар ўзларига нисбатан). Бундай усулга турғун саралаш дейилади. 
Саралаш самарадорлигини бир неча мезонлар бўйича баҳолаш мумкин: 

саралашга кетган вақт; 

саралаш учун талаб қилинган оператив хотира; 

дастурни ишлаб чиқишга кетган вақт. 
Биринчи мезонни қараб чиқайлик. Саралаш бажарилганда таққослашлар ёки алмаштиришлар сони 
ҳисоблаш мумкин.. 
Фараз қилайлик, Н = 0,01n
2
+ 10n – таққослашлар сони. Агар n < 1000 бўлса, у ҳолда иккинчи 
қўшилувчи катта, акс ҳолда яъни, n > 1000 бўлса, биринчи қўшилувчи катта бўлади. 
Демак, кичкина n ларда таққослашлар сони n га тенг бўлади, катта n ларда эса n
2
га тенг бўлади. 
Саралашда таққослашлар сони қуйидаги оралиқларда бўлади: 


n
n
O log
дан 
 
2
n
O
гача; 
 
n
O
– идеал ҳолатда. 
Саралашни қуйидагича усуллари бор: 

қатъий (тўғридан-тўғри) усуллар; 

яхшиланган усуллаш. 
Қатъий усулларни афзалликларини кўриб чиқайлик: 
1. Биламизки, дастурларни ўзлари ҳам хотирада жой эгаллайди. Тўғридан тўғри саралаш усулларини 
дастурлари қисқа бўлиб улар тушунишга осон.
2. Тўғридан тўғри саралаш усуллари орқали саралаш тамойилларининг асосий хусусиятларини 
тушунтириш қулай. 
3. Мураккаблаштирилган усулларда унча кўп амалларни бажариш талаб қилинмасада, ушбу 
амалларнинг ўзлари ҳам анча мураккабдир. Гарчи етарлича катта n ларда улардан фойдаланиш тавсия 
этилмасада, кичик n ларда мазкур усуллар тезроқ ишлайди. 
Шу жойни ўзида қатъий усулларни ишлаш тамойилларига кўра 3 та тоифага бўлиш мумкин: 
1. тўғридан-тўғри қўшиш усули (by insertion);
2. тўғридан-тўғри танлаш усули (by selection);
3. тўғридан-тўғри алмаштириш усули (by exchange).