Quicksort o se auala polokalame

I le 1960, atiina ae K. A. liusuavai ai se metotia mo le sailiili vave o faamatalaga, na avea ma e sili ona lauiloa. O aso nei ua lautele faaaogaina i le polokalame, e pei o loo i ai le tele o meatotino lelei: e mafai ona faaaoga mo tulaga aoao, e manaomia ai se faateleina laiti i le manatu faaopoopo, talafeagai ma ituaiga eseese o lisi ma faigofie ona faatino. Ae o loo drawbacks, lea ei Quicksort: faaaoga ai le galuega faatagaina a le tele o mea sese, ma e teisi femoumouai.

Ae peitai, o le lomiga e sili ona suesueina. Ina ua mavae le uluai Hoare totogiina, o le toatele faia ana suesuega mafiafia. na faatuina faavae tele i fesili faʻalemafaufau, o le mauaina o le taimi e faaalu i le galuega, lea e mafua ai i faamaoniga o ni faataitaiga. E talosaga moni e faaleleia ai le algorithm faavae ma le faateleina o le saoasaoa.

e matua tutusa Quicksort, e mafai ona maua i soo se mea. I lona tulaga o loo faatinoina le auala TList.Sort, taimi nei i lomiga uma (vagana 1) Delphi, o le galuega tauave faletusi o le taimi e alu ai e faamaea ai, qsort i C ++.

e mafai ona tuufaatasia le mataupu faavae autu o le faagaoioiga o se "vaevae ma e manumalo." E tupu pe a solia o le lisi i ni vaega se lua ma ua faavasegaina mo vaega e lava taitasi. E faapea e sili atu le gauai e tatau ona totogi atu i le faagasologa o le tuueseeseina, i le taimi lea e tulai mai: ua fuafuaina e se faavae elemene ma ua matua toe fesuiai lana lisi atoa. Fausia i le itu tauagavale o se vaega o sui tauva, o le taua o lea e itiiti ifo nai lo le tulafono le isi faaliliuina uma. E liliu atu o le elemene autu i le lisi faavasega i lona tulaga tonu. O le isi tulaga - o se luitau galuega tauave recursive sailiili mo itu uma e lua o le vaega e faatatau i le faavae. Ua iʻu ai le faagasologa o galuega pe afai o le lisi o loo i ai na elemene e tasi, o le a faavasega. O lea, ina ia mafai ona pulea o se galuega tauave polokalame e pei o se ituaiga vave, e tatau ai ina ia iloa le galuega o le algorithms maualalo o tulaga: a) le filifiliga o le tagata o le faavae; b) se lisi o le permutation sili ona lelei e maua ai seti e lua i le tulaga faatauaina laiti ma tetele.

Faamasani ma mataupu faavae muamua. Pe a filifilia le sui faavae, e tatau ona le naunauga lava o le a filifilia mai le lisi o le averesi lea. Ona i le malologa ua vaevaeina i ni afa tutusa lua. E fuafua le tau aogā averesi i le lisi e matua faigata lava, o lea bypasses le sailiili na saoasaoa e oo lava i lenei itu calculus. Ae o le filifiliga o le elemene autu i le taua aupito maualuga po o le maualalo - foi e le o le filifiliga sili ona lelei. I tulaga e le faaiuga o se tasi e faatupuina le a faamaonia lisi avanoa, ma le atoa lona lua. O lea la o le faaiuga e pei o le e tatau ona filifilia sui faavae se tasi e latalata atu i le averesi, ae i luga o le maualuga ma le maualalo.

Le taimi lava e fuafuaina se filifiliga, e mafai ona faagasolo i le algorithm decomposition. O lenei mea ua taʻua o loops totonu ituaiga vave. o loo fausia i mea uma i le faasino upu o igoa Avanoa lua vave: muamua alu i luga o le elemene mai le tauagavale i le taumatau, o le lona lua, i luga o le ese mai ai, mai le tauagavale i le taumatau. Amata taumatau faatinoga taotoga: le faasino upu o loo i le lisi ma faatusatusa i tulaga faatauaina uma i le autu. ua atoatoa le faataamilosaga pe e itiiti ifo le elemene nai lo pe tutusa i le fogaeleele. O le, o loo i ai se faatusatusaga ma e faaitiitia ai le taua o le faasino upu. I le lima tauagavale Ua uma e sili atu pe a le galuega nai lo le po o le aoga tutusa. Iinei, o le a faateleina le taua faatusatusaga.

I lenei tulaga o partitioning algorithm lea e aofia quicksort, e mafai ona tulai mai e lua tulaga. O le mea muamua e faapea e itiiti ifo nai lo le aia tatau o le faasino upu i luga o le itu tauagavale. O lenei faailoa se mea sese, ona o loo i ai elemene i lea na taua i totonu o le lisi o loo i le faasologa sese. Galuega Faatino - suia o latou nofoaga. O le tulaga lona lua o le taimi lea e tutusa uma o le koluma i po sopoia. faailoa mai ai se tuueseesega faamanuiaina lenei o le lisi, o lona uiga, o le taimi nei atoa le galuega.