Quicksort kā programmēšanas metodi

In 1960, K. A. sirms izstrādāja metodi ātrai šķirošanai informāciju, kļuva par slavenāko. Šodien tā ir plaši izmanto programmu, jo tas ir daudz pozitīvu īpašību: to var izmantot vispārējos gadījumos tas prasa nelielu pieaugumu papildu atmiņu, ir saderīga ar dažādiem sarakstiem un viegli īstenot. Bet ir trūkumi, kas ir quicksort: izmantojot darbs ļāva daudz kļūdas, un tas ir nedaudz nestabils.

Tomēr, tas ir visvairāk pētīta versiju. Pēc pirmā maksājuma HOARE, daudzi to tā blīvu pētījumu. liela bāze tika izveidota uz teorētiskiem jautājumiem, atrast laiku, kas pavadīts uz darbu, kura pamatā ir empīriskiem pierādījumiem. Tur bija reāli priekšlikumi, lai uzlabotu pamata algoritmu un lielāku ātrumu.

Quicksort ir ļoti bieži, to var atrast visur. Uz tās pamata metode ir ieviesta TList.Sort, pašreizējo visās versijās (izņemot 1) Delphi, bibliotēkas funkciju laiku, kas bija, lai pabeigtu, qsort C ++.

Pamata darbības princips var formulēt kā "skaldi un valdi". Tā notiek laužot sarakstu divās grupās, un ir sakārtoti katrai daļai ar sevi. No tā izriet, ka vairāk uzmanības jāpievērš sadalīšanas process, kura laikā notiek šādu: nosaka bāzes elements, un ir salīdzinoši pārkārtot visu savu sarakstu. Built pa kreisi grupas kandidātu, kuru vērtība ir mazāka nekā visu pārējo pārejas noteikumi. Izrādās, ka galvenais elements sakārtoti sarakstā ir tās pienācīgo vietu. Nākamais posms - izaicinājums rekursīvas kārtošanas funkcijas abās pusēs elementu attiecībā pret pamatni. Tā beidzas process darbojas tikai tad, ja sarakstā ir tikai viens elements, kas ir sakārtoti. Tādējādi, lai apgūtu programmēšanas funkcija kā ātra veida, ir nepieciešams zināt darbu zemākā līmeņa algoritmi: a) izvēle bāzes locekli; b) sarakstu visefektīvāko permutāciju ražot divas ar mazākiem un lielākiem vērtībām.

Iepazīties ar pirmajiem principiem. Izvēloties bāzes locekli, būtu ideālā gadījumā jāizvēlas no saraksta vidējā. Tad uz pārtraukuma ir sadalīta divās vienādās daļās. Tikai aprēķinātu vidējo vērtību sarakstā, ir ļoti grūti, tāpēc pat ātrākais šķirošanas apiet šo calculus pusē. Bet izvēle pamata elementa ar maksimālo vai minimālo vērtību - arī nav labākais risinājums. Gadījumā, ja šāda noteikšana viens rada tukšas saraksti tiks garantēta, un otrais pilna. Līdz ar to secinājums, ka bāzes locekli jāizvēlas vienu, kas ir tuvāk par vidējo, bet gan uz maksimālo un minimālo.

Kad izvēle ir noteikts, jūs varat doties uz sadalīšanās algoritmu. Šī tā saucamā iekšējā cilpas ātri kārtošanas. Viss ir balstīts uz divām ātrās piekļuves rādītājiem: vispirms doties pa elementiem no kreisās uz labo pusi, otro, gluži pretēji, no labās uz kreiso pusi. Sākas operācija izpildes tiesības: indekss ir sarakstā un salīdzināt visas vērtības uz galveno. Cikls ir pabeigta, kad elements ir mazāks par vai vienāds ar bāzes. Tas nozīmē, ka ir salīdzinājums un samazina vērtību indeksu. No kreisās puses, kad darbs ir pabeigts lielāka vai vienāda vērtība. Lūk, salīdzinājums vērtība palielinās.

Šajā posmā šķērssienu algoritmu, kas ietver quicksort divas situācijas var rasties. Pirmais ir tas, ka indekss pa kreisi ir mazāks nekā labi. Tas norāda uz kļūdu, tad ir elementi, uz kuriem tas tika norādīts sarakstā ir nepareizā secībā. Izeja - mainīt savas vietas. Otrā situācija ir tad, ja abas kolonnas ir vienāds ar vai šķērso. Tas norāda uz veiksmīgu atdalīšanu no saraksta, tas ir, darbs ir pabeigts.