Quicksort somunhu zvirongwa nzira

Muna 1960, K. A. anoparadzira muitiro kuti nokukurumidza Sorting mashoko, akava kupfuura akakurumbira. Nhasi chichiri kushandiswa mapurogiramu, sezvo ane zvizhinji zvakanaka zvivako: rinogona kushandiswa kungopa nyaya, zvinoda chiduku kuwedzera mamwe ndangariro, inowirirana marudzi akasiyana mazita uye nyore kushandisa. Asi pane zvainovhiringidzawo, iro rine Quicksort: kushandisa basa akabvumira yakawanda nezvikanganiso, uye yakati kusagadzikana.

Zvisinei, zviri zvikuru kudzidza Bhaibheri. Mushure wokutanga muripo Hoare, vakawanda vanoita gobvu kudzidza kwayo. guru garo kwakatangwa yokungotaura mibvunzo yokuwana nguva yakawandisa kubasa, uko underpinned nokuda empirical uchapupu. Paiva vaitaura chaidzo kuvandudza inokosha algorithm uye kwakawedzera nokukurumidza.

Quicksort kwakakurumbira chaizvo, zvinogona kuwanikwa pose pose. On kwayo hwaro nzira iri rakatangwa TList.Sort, chipo mushanduro zvose (kunze 1) Delphi, raibhurari kushanda nguva zvaida kupedza, qsort muna C ++.

Inokosha kushanda zvinogona akagadzira se "kamura uye vakundi". It rikauya kutyora zvawanyora mapoka maviri uye vari arongwe kuti chikamu chimwe nechimwe woga. It anotevera kuti pfungwa anofanira rwakabhadharwa kuna kuparadzana muitiro, umo zvinotevera kunoitika: ndezvipi zvaiva Kufananidzira uye tichishandisa rearranged yake yose pasi. Kuvakirwa rworuboshwe boka musarudzo, kukosha iyo idukusa vamwe kutapurirana mitemo. Zvakaratidza kuti huru chinhu chiri arongwe pamazita iri munzvimbo yayo. Rinotevera Danho - dambudziko recursive Sorting mashandiro kuti mativi ose zvinhu hama kuti hwaro. Painoguma muitiro inoshanda chete kana ndandanda ine chete chaikosha chete,. Ndiko kuti arongwe Saka, kuti tenzi zvirongwa chemuTestamente kukurumidza zvaro, zvinokosha kuziva basa repasi chechetere algorithms: a) kusarudza pechingoro nhengo; b) Nyora inonyatsobudirira permutation kubudisa nemhando mbiri duku uye hombe tsika.

Vanyatsoziva pamwe okutanga nenheyo. Pakusarudza mujinga nhengo, vanofanira Zvakanakisa kusarudzwa kubva mazita avhareji. Zvadaro musi kwemasikati iri huviri zvakaenzana sezvikamu. Just ngaaverenge avhareji ukoshi ari pamazita zvakaoma chaizvo, saka kunyange uchitsanya Sorting bypasses rwuno calculus. Asi rakasanangurwa pakati chinokosha pamwe kufadza kana shoma ukoshi - uyewo haana yakanakisisa kuzvipedza. Kana kutsunga mumwe akadaro pave chinhu mazita kuchaitwa, uye yechipiri zvizere. Nokudaro mhedziso kuti sezvo zvitsigiro nhengo zvinofanira kusarudzwa munhu pedyo paavhareji, asi kufadza uye zvishoma.

Kamwe chisarudzo anoratidzwa, unogona mberi kuti manyowa algorithm. Izvi zvinonzi yomukati zvishwe nokukurumidza ndokumwewo. Zvose inovakwa zviviri Rapid Access maindex: kutanga kuyambuka zvinhu kubva kuruboshwe kuenda kurudyi, wechipiri, nekusiyana, kubva kurudyi kuenda kuruboshwe. Kunotanga kushanda kuurayiwa kurudyi: indekisi iri pachikwata uye enzanisa ose tsika huru. The kutenderera zvakakwana kana chinhu idukusa kana kuenzana Muongororo yekutanga. Ndiko, pane fananidzo uye zvinoderedza kukosha indekisi. Kuruboshwe kana basa rapera mukuru kana kukosha zvakaenzana. Pano, fananidzo ukoshi inowedzerawo.

Panguva iyi partitioning algorithm iyo unotora quicksort, mamiriro ezvinhu maviri angamuka. Chokutanga ndechokuti indekisi kuruboshwe idukusa zvakarurama. Izvi zvinoratidza kutadza, saka pane zvinhu apo chakataurwa muna ndandanda vari isiri muhurongwa. Output - kushandura nzvimbo dzavo. The mamiriro wechipiri apo vaviri mbiru akaenzana kana vayambuka. Izvi zvinoratidza inobudirira kupatsanurwa pamazita, kureva basa zvino wakwana.