Quicksort kama njia ya programu

Mwaka 1960, K. A. Hoar alitengeneza utaratibu kwa ajili ya kuchagua kasi ya habari, akawa maarufu zaidi. Leo ni sana kutumika katika programu, kama ina mengi ya mali chanya: inaweza kutumika kwa ajili ya kesi ya jumla, inahitaji ongezeko dogo katika kumbukumbu ya ziada, sambamba na aina tofauti ya orodha na rahisi kutekeleza. Lakini kuna vikwazo, ambayo ina Quicksort: kwa kutumia kazi kuruhusiwa mengi ya makosa, na ni kiasi fulani msimamo.

Hata hivyo, ni toleo la hivi alisoma. Baada ya malipo ya kwanza Hoare, wengi kufanya utafiti wake vizuri kweli. kubwa ya msingi ilianzishwa juu ya maswali ya kinadharia ya kupata muda unaotumika katika kazi, ambayo ni inayounganishwa na ushahidi wa kisayansi. Kulikuwa na mapendekezo halisi ya kuboresha algorithm msingi na kuongezeka kasi.

Quicksort ni kawaida sana, inaweza kupatikana kila mahali. Kwa msingi wake mbinu inatekelezwa TList.Sort, sasa katika matoleo yote (isipokuwa 1) Delphi, maktaba kazi ya muda ilichukua kukamilisha, qsort katika C ++.

Kanuni ya msingi ya operesheni inaweza kuwa yaliyoandaliwa kama "kugawa na kushinda." Ni hutokea kuvunja orodha katika makundi mawili na ni yamepangwa kwa kila sehemu peke yake. Kwa sababu hiyo makini zaidi wanapaswa kulipwa kwa mchakato kujitenga, wakati ambao yafuatayo hutokea: imedhamiria kwa kipengele msingi na ina kiasi upya orodha yake yote. Kujengwa kwa upande wa kushoto wa kundi la wagombea, thamani ambayo ni chini ya sheria nyingine zote uhamisho. Ni zinageuka kuwa kipengele muhimu katika orodha yamepangwa katika nafasi yake halali. hatua ya pili - changamoto kujirudia kuchagua kazi kwa pande zote mbili za mambo jamaa msingi. Ni mwisho wa mchakato inafanya kazi tu ikiwa Orodha ina tu kipengele moja, kwamba ni kupangwa. Hivyo, ili bwana programu kazi kama aina ya haraka, ni muhimu kujua kazi ya mipangilio wa ngazi ya chini: a) uchaguzi wa mwanachama msingi; b) orodha ya permutation ya ufanisi zaidi wa kuzalisha seti mbili na maadili ndogo na kubwa.

Familiarize na kanuni ya kwanza. Wakati wa kuchagua mwanachama msingi, lazima walau kuchaguliwa kutoka orodha ya wastani. Kisha juu ya mapumziko imegawanywa katika sehemu mbili sawa. Tu mahesabu thamani ya wastani katika orodha ni vigumu sana, hivyo hata kuchagua kasi Mataro pande huu calculus. Lakini uchaguzi wa kipengele msingi na thamani ya juu ama chini - pia si chaguo bora. Katika kesi ya uamuzi huo wa moja inajenga orodha tupu itakuwa uhakika, na wa pili kamili. Hivyo hitimisho kwamba kama mwanachama msingi unapaswa kuchaguliwa moja ambayo ni karibu na wastani, lakini kwa kiwango cha juu na kima cha chini.

Mara baada ya uchaguzi imedhamiria, unaweza kuendelea na kuoza algorithm. Hii kinachojulikana mizunguko ndani aina ya haraka. Kila kitu ni kujengwa juu ya mbili Access bahati Rapid: kwanza kwenda juu ya mambo kutoka kushoto kwenda kulia, pili, kinyume chake, kutoka kulia kwenda kushoto. Huanza kazi utekelezaji sahihi: index iko kwenye orodha na kulinganisha thamani zote kuu. mzunguko ni kamili wakati kipengele ni chini ya au sawa na msingi. Hiyo ni, kuna kulinganisha na kupungua thamani ya index. Kwa upande wa kushoto wakati kazi ni kumaliza zaidi au thamani sawa. Hapa, kulinganisha thamani kuongezeka.

Katika hatua hii ya partitioning algorithm ambayo inajumuisha quicksort, hali mbili yanaweza kutokea. kwanza ni kwamba ripoti ya kushoto ni chini ya sahihi. Hii inaonyesha makosa, basi kuna mambo ambayo ni ilivyoelezwa katika orodha zinafanya vibaya. Pato - mabadiliko ya maeneo yao. hali ya pili ni wakati wote wa safu ni sawa au shilingi. Hii inaonyesha mgawanyo wa orodha na mafanikio, ambayo ni, kazi ni sasa kamili.