Амалисозии алгоритми ҷустуҷӯ

Сарсухан

Дар солҳои охир барномасозӣ барои компютерҳо на танҳо асбобе гардид, ки доштани он барои кори муваффақиятнок дар бисёр соҳаҳои татбиқ ҳалкунанда, балки ба мавзӯи омӯзиши илмӣ низ табдил ёфтааст. Маълум шуд, ки қарор дар бораи сохтори додаҳо бе донистани алгоритмҳо қабул карда намешавад. Инчунин, сол то сол ҳаёт тезтар мешавад, ҷараёни иттилоот суръат ва афзоиш меёбад. Барои нигоҳ доштани ҳама намуди иттилоот, ба истилоҳ пойгоҳи додаҳо истифода мешаванд. Аммо ҳатто бо ин пойгоҳи додаҳо, хусусан агар онҳо миллионҳо нуқтаҳоро дар бар гиранд, кор кардан хеле душвор аст, ҳатто гуфтан мумкин нест. Бе навъбандӣ ҷудо кардани чунин миқдори зиёди маълумот қариб ғайриимкон аст, онҳо ба мо имкон медиҳанд, ки маълумоти заруриро аз маҷмӯи пешакӣ фармоишшуда нисбатан зуд ва самаранок истихроҷ кунед. Аз ин рӯ, усулҳои ҷудокунӣ хеле муҳиманд, махсусан ҳангоми коркарди маълумот. Дар барномасозӣ ба навъҳо ва алгоритмҳои онҳо таваҷҷӯҳи зиёд дода мешавад.

Дар айни замон, як қатор алгоритмҳои ҷудокунӣ мавҷуданд, ки хусусият ва суръати коркарди информатсияро доранд. Аммо, бисёре аз онҳо як камбудии хеле ҷиддӣ доранд, яъне вақти иҷрои онҳо ба квадрати шумораи элементҳо мутаносиб аст. Барои миқдори зиёди маълумот, ин навъҳо суст хоҳанд буд ва аз қимати муайян сар карда, онҳо хеле суст хоҳанд буд, то амалӣ бошанд.

Дар ин кори дипломии мо яке аз беҳтарин навъҳоро баррасӣ хоҳем кард. Ки онро зуд навъбандӣ меноманд, алгоритми он беҳтарин эътироф шудааст.

Мақсади таҳияи кори дипломӣ омӯзиши технологияҳои муосири барномасозӣ ва таҳлили алгоритми массиви иҷроиши масъалаҳои тавассути алгоритми Хоар мебошад.

Мақсади умумии таҳияи кори курсӣ:

1. Асосҳои назариявии алгоритмҳои ҷудокуниро меомӯзед;

2. Алгоритми ҷудокунии фрагментии Хоарро дида мебароем;

3. Алгоритми мазкурро бо забони барномасозӣ амалӣ месозем;

4. Таҳлили алгоритмро ба навъҳо ҷудо ҷудо мекунем.

Боби 1. Ҷанбаҳои асосии назариявии кори  алгоритми Хоар

1.1. Мафҳуми алгоритм ва ҷустуҷӯ

Алгоритм ҳама гуна тартиби ҳисоббарории дақиқ муайяншуда мебошад, ки баъзе қимат ё маҷмӯи қиматҳоро ҳамчун вуруд қабул мекунад ва боиси қимати баромад ё маҷмӯи қиматҳо мегардад. Ҳамин тариқ, алгоритм як пайдарпаии қадамҳои ҳисоббарорӣ мебошад, ки қиматҳои воридшударо ба баромадҳои баромад табдил медиҳанд.

Алгоритмро инчунин метавон ҳамчун асбобе баррасӣ кард, ки барои ҳалли як масъалаи ҳисоббарории хуб гузошта шудааст. Алгоритм тартиби мушаххаси ҳисобкуниро тавсиф мекунад, ки тавассути он ба иҷрои ин муносибатҳо ноил шудан мумкин аст.

Масалан, мо метавонед пайдарпайии рақамҳоро бо тартиби камнашаванда ҷудо кунед. Ин масъала аксар вақт дар амал ба миён меояд ва барои шиносоӣ бо намунаи он бо бисёр усулҳои стандартии таҳия ва таҳлили алгоритмҳо заминаи мусоид мебошад.

Мураттабкунӣ раванди тартиб додани маҷмӯи объектҳои иттилоотии шабеҳ бо тартиби афзоиш ё камшавии қиматҳои онҳо мебошад. Масалан, рӯйхати L аз n элементҳо бо тартиби афзоиши қиматҳои элементҳо мураттаб карда мешаванд, агар L1 <= L2 <= ... <= Ln бошад.