Quicksort ҳамчун усули барномасозии

Дар соли 1960, К. А. Hoar усули барои мураттабсозии босуръати иттилоот тањия, ки машҳур гашт. Имрӯз он аст, ба таври васеъ дар барномасозӣ истифода бурда мешавад, ки ба он дорад, бисёр объектҳои мусбат: он метавонад барои ҳолатҳои умумӣ истифода бурда, аз он талаб афзоиши хурд дар хотираи иловагӣ, мувофиқ бо намудҳои гуногуни рӯйхати ва осон ба амалӣ менамояд. Вале аз норасоиҳои он ҷо, ки дорои Quicksort: бо истифода аз кори иҷозат бисёр хато, ва онро то ҳадде ноустувор аст.

Бо вуҷуди ин, он нусхаи бештар омӯхта мешавад. Пас аз он ки аввалин Hoare пардохт, бисёр омӯзиши зиччи худ мекунед. пойгоҳи калон оид ба масъалаҳои назариявӣ дарёфти вақт сарф оид ба кор, ки аз ҷониби Таљрибањо пуштибонӣ таъсис дода шуд. буданд, пешниҳодҳои воқеӣ ба беҳтар намудани алгоритми асосӣ ва баланд бардоштани суръат нест.

Quicksort хеле маъмул аст, ки он метавонад дар ҳама ҷо ёфт. Дар заминаи он усули TList.Sort, айни замон дар тамоми версияҳои (ба истиснои 1) Delphi, вазифаи китобхона вақт онро анҷом, qsort дар C ++ амалӣ карда мешавад.

Принсипи асосии фаъолияти метавонад ҳамчун «холигоҳи ва забт» мураттаб. Он рух шикастани рӯйхат ба ду гурӯҳ доранд ва барои ҳар як қисми худи мураттаб. Аз ин бармеояд, ки диққати бештар бояд ба раванди ҷудоӣ, ки дар давоми он зерин рух пардохта мешавад: аз ҷониби як унсури пойгоҳи муайян ва нисбатан rearranged рӯйхати пурраи худ. Сохта ба чап як гурӯҳи номзадҳо, ки арзиши он нисбат ба ҳамаи қоидаҳои интиқоли дигар аст. Он рӯй, ки унсури асосии дар рӯйхат мураттаб дар ҷои қонунии он аст. Дар марҳилаи навбатӣ - мушкилоти функсияи рекурсиви мураттабсозии барои ҳар ду ҷониб аз унсурҳои нисбат ба пойгоҳи. Ин хотима раванди кор танҳо агар рӯйхат дорои танҳо як унсури он аст, ки ба мураттаб карда мешавад. Ҳамин тариқ, бо мақсади азхуд кардани функсия барномасозӣ ҳамчун як навъ зуд, зарур аст, ки ба бидонед, кори алгоритмҳои сатҳи поёнӣ: а) интихоби узви пойгоҳи; б) рӯйхати куниро самараноки истеҳсоли ду маҷмӯи бо арзишҳои хурдтар ва калонтар аст.

Шиносоӣ бо принсипҳои аввал. Ҳангоми интихоби аъзои пойгоҳи, идеалӣ бояд аз рӯйхати миёнаи интихоб карда мешаванд. Он гоҳ дар бораи танаффус ба ду маѓзи баробар тақсим карда мешавад. Танҳо ҳисоб арзиши миёнаи дар рӯйхат хеле мушкил аст, барои ҳамин ҳам босуръат мураттабсозии селпартоњо ин тараф ҳисоби. Аммо интихоби унсури асосии бо арзиши ҳадди ақали ё - низ нест, беҳтарин вариант. Дар сурати чунин муайян намудани яке аз меорад рӯйхати холӣ шавад, кафолат дода хоҳад шуд, ва дуюм пурра. Аз ин рӯ ба хулосае омаданд, ки ба сифати аъзои пойгоҳи бояд интихоб шавад, яке он аст, ки ба ҳисоби миёна наздик, вале дар ҳадди ва ҳадди ақалли.

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

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