Quicksort as Programming metoade

Yn 1960, K. A. Hoar ûntwikkele in metoade foar it flugge sortearring fan ynformaasje, waard it meast ferneamd. Hjoed It wurdt in protte brûkt yn de programmearring, lykas it hat in protte positive eigenskippen: it kin brûkt wurde foar algemiene gefallen, it fereasket in lytse ferheging fan 'e ekstra ûnthâld, kompatibel mei ferskillende soarten lysten en maklik te fieren. Mar der binne skaadkanten, dat hat Quicksort: mei help fan wurk tastien in soad flaters, en it is wat ynstabyl.

It is lykwols it meast ûndersochte ferzje. Nei de earste betelling Oberman, in protte dwaan har ticht stúdzje. grut basis waard oprjochte op teoretyske fragen fan it finen fan de tiid bestege oan 'e baan, dat wurdt underpinned troch empirysk bewiis. Der wiene echte útstellen te ferbetterjen de basis algoritme en ferhege snelheid.

Quicksort is hiel gewoan, dan fine jo oeral. Op syn grûn de metoade wurdt ymplemintearre TList.Sort, oanwêzich yn alle ferzjes (útsein 1) Delphi, de bibleteek funksje fan tiid duorre it te foltôgjen, qsort yn C ++.

Utgongspunt fan operaasje kin wurde formulearre as in "ferdiel en hearskje". It ûntstiet brekken de list yn twa groepen en wurde sortearre foar elk diel troch himsels. It folget dat der mear omtinken wêze moatte foar de ôfskieding proses, wêrby't de neikommende plakfynt: wurdt bepaald troch in basis elemint en is relatyf oardere syn hiele list. Boud lofts fan in groep fan kandidaten, de wearde dêrfan is minder as alle oare oerdracht regels. It docht bliken dat it wichtichste elemint yn de sortearre list is yn syn rjochtmjittige plak. De folgjende poadium - in útdaging rekursive sortearring funksjes foar beide kanten fan de eleminten relatyf oan de basis. It einiget it proses wurket allinne as de list befettet mar ien elemint, dat is te sortearre wurde. Sa, om te behearskjen in programmearring funksje as in snelle soarte, is it nedich te witten it wurk fan legere-nivo Algorithmen: a) de kar fan de basis member; b) in list fan de meast effektive permutation te produsearjen twa sets mei lytsere en gruttere wearden.

Fertroud mei earste prinsipes. Wannear't kiezen de basis lid, moatte ideale situaasje wurde selektearre út de list fan gemiddelde. Dan op it skoft wurdt ferdield yn twa likense helten. Krekt berekkene de gemiddelde wearde yn 'e list is hiel dreech, dus sels de snelste sortearring rûnwegen dit kalkulus kant. Mar de kar fan 'e fûnemintele elemint mei de maksimale of minimale wearde - ek net de bêste opsje. Yn gefal sa'n beslissing fan ien skept lege listen wurdt garandearre, en de twadde fol. Dêrfandinne de konklúzje dat as de basis lid moat keazen wurde ien, dat is tichter by de gemiddelde, mar op it maksimum en minimum.

Ien kear in kar wurdt bepaald, kinne jo trochgean oan it ûntleden algoritme. Dit saneamde ynderlike loops flugge sort. Alles wurdt boud op twa Rapid Tagong yndeksearret: earst gean oer de eleminten fan links nei rjochts, de twadde, krekt oarsom, fan rjochts nei lofts. Begins operaasje útfiering rjochts: de yndeks stiet op de list en ferlykje alle wearden oan de wichtichste. De syklus is folslein as it elemint is minder as of gelyk oan de nulmjitting. Dat wol sizze, der is in ferliking en sakket de wearde fan de yndeks. Oan de linker kant doe't it wurk klear is grutter as of gelyk wearde. Hjir, de ferliking wearde wurdt grutter.

By dizze faze fan partitioning algoritme dat bestiet út Quicksort, twa situaasjes ûntstean. It earste is dat de yndeks op 'e linker is minder as rjocht. Dat wiist in flater, dan binne der eleminten dy't neffens it waard ferklearre yn de list binne yn de ferkearde folchoarder. Útfier - feroarje harren plakken. De twadde situaasje is doe't beide fan 'e pylder is gelyk oan of oerstutsen. Dat wiist op in súksesfol ôfskieding fan 'e list, dat is, it wurk is no klear.