|
ЎЗБЕКИСТОН АЛОҚА ВА АХБОРОТЛАШТИРИШ АГЕНТЛИГИ
МУҲАММАД АЛ-ХОРАЗМИЙ НОМИДАГИ ТОШКЕНТ АХБОРОТ ТЕХНАЛОГИЯЛАРИ УНИВЕРСИТЕТИ
“Ахборот техналогиялари” факультети
“Ахборот техналогияларини дастурий таъминоти” кафедраси
“Маълумотлар тузилмаси ва алгоритмлар” фани
Мавзу: Саралаш тушинчаси ва алгоритмлар. Саралашнинг қатъий усуллари.
Бажарди: 023-18 гуруҳ, 3-курс талабаси
Уринова Ҳуррият Баҳроновна
Мавзу:Саралаш тушинчаси ва алгоритмлар. Саралашнинг қатъий усуллари.
Режа:
1. Саралаш тушунчаси, унинг турлари.
2. Тўғридан тўғри қўшиш орқали саралаш.
3. Тўғридан тўғри танлаш орқали саралаш.
4. Тўғридан тўғри алмаштириш орқали саралаш.
5. Саралашнинг яхшиланган усуллари.
Калитли сўзлар: саралаш, ички саралаш, ташқи саралаш, регулярлик,
саралаш самарадорлиги, қўшиш орқали саралаш, танлаш орқали саралаш,
алмаштириш орқали саралаш (пуфаксимон саралаш), тез саралаш, шелл
саралаши.
Саралаш – бу берилган тўплам элементларини бирор бир тартибда
жойлаштириш жараёнидир. Саралашни мақсади тартибланган тўпламда
керакли элементни топишни осонлаштиришдан иборат. Саралаш
дастурларни трансляция қилинаётганда, маълумотлар мажмуасини ташқи
хотирада ташкил қилинаётганда, кутубхоналар, каталоглар, маълумотлар
базаси яратилаётганда тадбиқ қилинади. Маълумки, саралашнинг турли ҳил
алгоритмлари мавжуд. Сабаби, битта масалани саралаш учун жуда кўплаб
турли ҳил алгоритмлардан фойдаланиш мумкин. Берилган масалани ҳал
қилишда баъзилари мукаммал бўлиши мумкин. Шунинг учун саралаш
масаласида алгоритмларни қиёсий таҳлилини ўтказиш зарурати пайдо
бўлади.
Саралаш масаласини қўйилишини қуйидагича ёзиш мумкин.
Фараз қилайлик, а1, а2 ,…, аn, элементлар кетма-кетлиги берилган
бўлсин. У ҳолда саралаш алгоритми элементларни массивга шундай
жойлаштирадики, натижада улар қандайдир муносабатга нисбатан
f(ак1) f(ак2) … f(акn) тартибга эга бўлади. Одатда f тартиблаш функцияси
қандайдир махсус қоида билан ҳисобланмасдан, балки элементни калит
қиймати бўйича массив элементлари тартибланади.
Маълумотларга қайта ишлов берилаётганда маълумотни информацион
майдонини ҳамда уни машинда жойлашишини (адресини) билиш зарур.
Саралашни иккита тури мавжуд: ички ва ташқи:
- ички саралаш бу оператив хотирадаги саралаш;
- ташқи саралаш – ташқи хотирада саралаш.
Саралаш бу маълумотларни калитлари бўйича хотирада регуляр
кўринишда жойлаштиришдир. Регулярлик деганда маълумотлар калит
қийматлари бўйича массивда бошидан охиригача ўсиши ёки камайиши
тушинилади.
Агар сараланаётган ёзувлар хотирада катта хажмни эгалласа, у ҳолда
уларни алмаштиришлар катта сарф (вақт ва хотира маъносида) талаб қилади.
Ушбу сарфни камайтиши мақсадида, саралаш калитлар адреси жадвалида
амалга оширилади. Бунда фақатгина маълумот кўрсаткичлари
алмаштирилиб, массив ўз жойида қолади. Юқоридаги усул адреслар
жадвалини саралаш усули дейилади.
Сараланаётганда бир ҳил калитлар учраши мумкин, бу ҳолда
сараланагандан кейин бир ҳил калитлилар бошланғич тартибда қандай
жойлашган бўлса, ушбу тартибда қолдирилиши мақсадга мувофиқ бўлади
(Бир ҳил калитлилар ўзларига нисбатан). Бундай усулга турғун саралаш
дейилади.
Саралаш самарадорлигини бир неча мезонлар бўйича баҳолаш мумкин:
саралашга кетган вақт;
саралаш учун талаб қилинган оператив хотира;
дастурни ишлаб чиқишга кетган вақт.
Биринчи мезонни қараб чиқайлик. Саралаш бажарилганда
таққослашлар ёки алмаштиришлар сони ҳисоблаш мумкин.
Фараз қилайлик, Н = 0,01 n2 + 10n – таққослашлар сони. Агар n < 1000 бўлса, у ҳолда иккинчи қўшилувчи катта, акс ҳолда яъни, n > 1000 бўлса, биринчи қўшилувчи катта бўлади.
Демак, кичкина n ларда таққослашлар сони n га тенг бўлади, катта n
ларда эса n2 га тенг бўлади.
Саралашда таққослашлар сони қуйидаги оралиқларда бўлади:
0(n log n) дан 0 (n2) гача; 0 (n) – идеал ҳолатда.
Саралашни қуйидагича усуллари бор:
қатъий (тўғридан-тўғри) усуллар;
яхшиланган усуллар.
Қатъий усуллар:
тўғридан-тўғри қўшиш усули;
тўғридан-тўғри танлаш усули;
тўғридан-тўғри алмаштириш усули.
Юқорида келтирилган учала усулда ҳам алмаштиришлар сони деярли бир ҳил бўлади.
Do'stlaringiz bilan baham: |
