Quicksort ka mokhoa mananeo

Ka 1960, K. A. Hoar ntshetswa pele mokhoa bakeng sa hlopha e potlakileng ea boitsebiso, e ile ea e tummeng ka ho fetisisa. Kajeno ho e ho pharaletseng sebelisitsoeng ka mananeo a, ha e ntse e na le e ngata ea thepa-positive: e ka sebelisoa bakeng sa ho sebetsana le linyeoe kakaretso, ho hloka le keketseho e nyenyane ya memori eketsehileng, e lumellana le mefuta e fapaneng ya mananeo le bonolo ho kenya. Empa ho na le haelloang teng, le nang le Quicksort: sebelisa mosebetsi oa lumelloa a mangata liphoso, 'me e ke a batla a sa tsitsang.

Leha ho le joalo, ho ke ke phetolelo ea ho fetisisa o ile a ithuta. Ka mor'a hore tefello ya pele Hoare, ba bangata ba etsa ho ithuta lona le letšo-letšo. kgolo botlaaseng ho ile ha thehoa ka lipotso mogopolofela ea ho fumana nako eo ile a qeta ka mosebetsi, e leng e tshegeditswe ke bopaki bo bontšang bonahetseng. Ho ne ho ditshitshinyo sebele ho ntlafatsa-tharabololo mantlha le e ile ea eketseha ka lebelo.

Quicksort ho tloaelehile haholo, e ka fumanoa hohle. Ka motheong oa lona mokhoa e kenngwa tshebetsong TList.Sort, joale liphetolelong tsohle (ntle le 1) Delphi, laebrari mosebetsi wa nako ho ile ha nka hore a phethe, qsort ka C ++.

The ea motheo ea ho sebetsa ka rerileng ka "arola le hlola ka". Ho etsahalang roba Lethathamong le ka lihlopha tse peli tse le ba aroloa ho karolo ka 'ngoe ke ka boeona. Ho latela hore tlhokomelo e eketsehileng e lokela ho leshwa ho tshebetso karohano, e leng nakong eo e latelang ho etsahala: e behilweng ke elements botlaaseng le e batlang e le rearranged lethathamo la hae kaofela. Hahiloeng ka ho le letsehali ea sehlopha sa bonkgetheng, boleng la e tlase ho ka melao e meng eohle phetiso. E fellang kateng le hore e elements sehloohong lethathamo aroloa e sebakeng sa eona se loketseng. Mokhahlelo latelang - phephetso recursive hlopha mesebetsi ya mahlakoreng ka bobeli a thepa ea motheo e amanang le ho botlaaseng. E qetella tshebetso sebetsa feela ha lethathamo la e na le feela karolo ea 'ngoe, e le hore ke lokela ho aroloa. Kahoo, e le ho li tseba e le mananeo a mosebetsi e le mofuta ka potlako, ho ke ke ho hlokahala hore ho tseba ka mosebetsi oa dikgatotharabololong tlaase-boemo ba: a) le ho khetha setho botlaaseng; b) lethathamo la permutation atlehang ka ho fetisisa ho fana ka lihlopha tse peli le melao ea boitšoaro e nyenyane le tse khōlō.

Tlwaelanya le melao-motheo ea pele. Ha re khetha ho setho botlaaseng, ba lokela ho sebakeng se loketseng a khetha ho tswa lenaneng la karolelano. Ka nako eo khefu e arotsoe ka dihalofo tse pedi tse lekanang. Feela a bale boleng karolelano ka lethathamo ke thata haholo, kahoo esita le ho hlopha lebelo ka ho fetisisa bypasses ena lehlakoreng calculus. Empa le ho khetha ya elements motheo le boleng ba palo e kahodimodimo kapa bonyane - hape ha khetho ea khomo. Tabeng ikemiselitse ho etsa joalo ba e mong baka mananeo letho tla Guaranteed, 'me ea bobeli e tletseng. Ka hona ho etsa qeto ea hore e le setho botlaaseng lokela ho khethoa eena e haufi le karolelano, empa ka palo e kahodimodimo le bonyane.

Hang lokela ho etsa khetho e ikemiselitse, u ka tsoela pele ho li bole kapele-tharabololo. Sena seo ho thoeng ke loops ka hare mofuta kapele. Tsohle e hahoa tse peli Phihlelo index ka potlako: pele ee thepa ea motheo e ho tswa ho letšehali ho ea ho le letona, ka bobeli, ho fapana le hoo, ho tloha lehlakoreng le letona la ho tsamaea. Qala tshebetso ho phetha ho le letona: index e ka lethathamo le bapisa makgabane tsohle tse khōlō. Potoloho ea bona li feletseng ha elements e ka tlase ho kapa lekanang ya motheo wa. Ke hore, ho na le ho ipapisa le decreases boleng ba li-index ya. Ka letsohong le letšehali ha mosebetsi o phethiloe boholo ho feta kapa boleng bo lekanang. Mona, ka papiso boleng eketseha.

Mothating ona oa partitioning-tharabololo eo kenyelletsa ditokiseletso quicksort, maemo a mabeli a ka hlahang. Ea pele ke hore index ka ho le letšehali le ka tlaase ho le letona. Sena se bontša phoso, joale ho na le likarolo tseo e ne e ile ea re ka lethathamo la tse ka odara e fosahetseng. Khumo - fetola libakeng tsa tsona. Boemo bobeli ke ha bobeli ba lenaneng la e lekanang kapa a tšela. Sena se bontša ka karohano ea lethathamo le atlehileng, ke hore, mosebetsi ke hona joale ka ho feletseng.