Quicksort bilang paraan programming

Noong 1960, K. A. Patandain nakabuo ng isang pamamaraan para sa mabilis na pag-uuri ng impormasyon, ay naging ang pinaka-tanyag na. Ngayon malawakan ito ay ginagamit sa programming, tulad ng ito ay may isang pulutong ng mga positibong katangian: maaari itong gamitin para sa pangkalahatang mga kaso, ito ay nangangailangan ng isang maliit na pagtaas sa ang mga karagdagang memory, katugma sa iba't ibang uri ng mga listahan at madaling ipatupad. Ngunit may mga drawbacks, na may Quicksort: gamit sa trabaho pinahihintulutan ng isang pulutong ng mga pagkakamali, at ito ay medyo hindi matatag.

Gayunman, ito ay ang pinaka-aral na bersyon. Matapos ang unang Hoare pagbabayad, marami ang kanyang siksik na pag-aaral. malaking base ay itinatag sa mga maximum na mga katanungan ng paghahanap ng mga oras na ginugol sa trabaho, na kung saan ay underpinned sa pamamagitan ng tunay na katibayan. May mga tunay na mga panukala upang mapabuti ang mga pangunahing algorithm at nadagdagan bilis.

Quicksort ay napaka-pangkaraniwan, maaari itong matagpuan kahit saan. Sa mismong batayan ang paraan ay ipinatupad TList.Sort, naroroon sa lahat ng mga bersyon (maliban 1) Delphi, ang library function ng oras na ito kinuha upang makumpleto, qsort sa C ++.

Ang mga pangunahing prinsipyo ng operasyon ay maaaring formulated bilang isang "hatiin at lupigin". Ito ay nangyayari paglabag sa listahan sa dalawang grupo at ay pinagsunod-sunod para sa bawat bahagi ng sarili nito. Ito ay sumusunod na ng higit na pansin ay dapat bayaran sa proseso ng paghihiwalay, kung saan naganap ang sumusunod: ay natutukoy sa pamamagitan ng isang batayang sangkap at ay relatibong rearranged ang kanyang buong listahan. Nakapaloob sa kaliwa ng isang grupo ng mga kandidato, ang halaga ng kung saan ay mas mababa kaysa sa lahat ng iba pang mga panuntunan transfer. Ito ay lumiliko out na ang pangunahing sangkap sa ang pinagsunod-sunod na listahan ay nasa kanyang nararapat na lugar. Ang susunod na yugto - isang hamon recursive pag-uuri function para sa parehong panig ng ang mga elemento na may kaugnayan sa base. Ito ay nagtatapos ang proseso ay gumagana lamang kung ang listahan ay naglalaman lamang ng isang elemento, iyon ay upang maging inayos. Kaya, upang makabisado isang programming function na bilang isang mabilis-uuri, ito ay kinakailangan upang malaman ang trabaho ng mas mababang antas algorithm: a) ang pagpili ng mga miyembro base; b) ang isang listahan ng mga pinaka-epektibong permutasyon upang makabuo ng dalawang set na may mas maliit at mas malaking halaga.

Maging pamilyar sa mga unang prinsipyo. Kapag pumipili ang batayang miyembro, dapat may perpektong mapili mula sa listahan ng mga average. Pagkatapos ay sa pahinga ay nahahati sa dalawang katumbas halves. Lamang kalkulahin ang average na halaga sa listahan ay napakahirap, kaya kahit ang pinakamabilis na pag-uuri bypasses ito calculus side. Ngunit ang pagpipilian sa mga pangunahing elemento na may maximum o minimum na halaga - hindi rin ang pinakamahusay na pagpipilian. Sa kasong tulad pagpapasiya ng isa ay lumilikha ng walang laman na listahan ay garantisadong, at ang pangalawang puno. Kaya ang konklusyon na bilang ng miyembro base ay dapat na pinili ang isa na ay mas malapit sa average, ngunit sa maximum at minimum.

Sa sandaling ang isang pagpipilian ay tinutukoy, maaari mong tumuloy sa agnas algorithm. Ang tinatawag na inner loop mabilis na pag-uuri. Lahat ng bagay ay binuo sa dalawang Rapid Access index na ito: unang pumunta sa ibabaw ng mga elemento mula kaliwa hanggang kanan, pangalawa, sa laban, mula kanan pakaliwa. Nagsisimula na operasyon execution tama: ang index ay sa listahan at ihambing ang lahat ng mga halaga sa main. cycle ay kumpleto na kapag ang sangkap ay mas mababa sa o katumbas ng baseline. Iyon ay, mayroong isang paghahambing at bumababa ang halaga ng index. Sa kaliwang kapag ang trabaho ay tapos na mas malaki kaysa sa o katumbas ng halaga. Narito, ang paghahambing na halaga ay nagtataas.

Sa yugtong ito ng partitioning algorithm na binubuo quicksort, dalawang mga sitwasyon maaaring lumabas. Ang una ay na ang index sa kaliwa ay mas mababa kaysa sa kanan. Ito ay nagpapahiwatig ng isang error, pagkatapos ay may mga elemento kung saan ito ay nakasaad sa listahan Nasa maling pagkakasunud-sunod. Output - baguhin ang kanilang mga lugar. Ang ikalawang sitwasyon ay kapag ang parehong mga haligi ay katumbas ng o crossed. Ito ay nagpapahiwatig ng isang matagumpay na paghihiwalay ng listahan, iyon ay, ang gawa ay ngayon kumpleto na.