Ātrā šķirošana kā programmēšanas metode
1960. gadā K.A. Hoare 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 šī ir visvairāk izpētītā versija. Pēc pirmā Hāra aprēķinu parādīšanās daudzi iesaistījās viņas blīvā pētījumā. Tika izveidota liela bāze par teorētiskiem jautājumiem, kā atrast darbu pavadīto laiku, ko atbalstīja empīriskie dati. Bija reāli priekšlikumi, kā uzlabot galveno algoritmu un palielināt darba ātrumu.
Ātrā šķirošana ir ļoti izplatīta, jūs varatsanāk 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 ++.
Darba pamatprincips var tikt formulēts kā"sadalīt un iekarot." Saraksta iedalījums ir divās grupās, un katrai daļai tiek veikta šķirošana atsevišķi. No tā izriet, ka ir jāpievērš lielāka uzmanība atdalīšanas procesam, kura laikā rodas šāds gadījums: tiek noteikts bāzes elements un viss saraksts jau ir pārvietots attiecībā pret to. Kreisajā pusē veidojas kandidātu grupa, kuras vērtības ir mazākas, bet pārējie tiek pārvietoti pa labi. Izrādās, ka šķirotajā sarakstā galvenais elements atrodas tā likumīgajā vietā. Nākamais solis ir izsaukt rekursīvo kārtošanas funkciju elementu abām pusēm, salīdzinot ar bāzi. Darba process beidzas tikai tad, ja sarakstā ir tikai viens elements, tas ir, tas tiks sakārtots. Tādējādi, lai apgūtu šādu programmēšanas funkciju kā ātru šķirošanu, jums jāzina apakšējā līmeņa algoritmu darbība: a) bāzes elementa izvēle; b) visefektīvākā saraksta maiņa, lai iegūtu divus komplektus ar mazākām un lielākām vērtībām.
Mēs iepazīsimies ar pirmā principa principiem. Izvēloties bāzes elementu, ideālā gadījumā no saraksta jāizvēlas vidējais. Tad, kad salauzta, tas tiek sadalīts divās vienādās daļās. Tikai aprēķināt vidējo vērtību sarakstā ir ļoti grūti, tāpēc pat visātrākā šķirošana apiet šo aprēķinu blakus. Bet izvēle galveno elementu ar maksimālo vai minimālo vērtību arī nav labākā izvēle. Šāda definīcija garantē, ka viens no izveidotajiem sarakstiem ir tukšs, bet otrais - pārpildīts. Tādēļ secināms, ka kā bāzes elementam jāizvēlas tāds, kas ir tuvāks vidējam, bet tālāk no maksimālā un minimālā.
Kad esat nolēmis izvēlēties, jūs varatdodieties uz sadalīšanas algoritma darbu. Tie ir tā saucamie iekšējie ātrās kārtības cikli. Viss ir balstīts uz diviem ātras darbības rādītājiem: pirmais sekos elementiem no kreisās uz labo pusi, otrā - otrādi, no labās uz kreiso pusi. Sākas izpildes darbība pa labi: indekss iet caur sarakstu un salīdzina visas vērtības ar galveno. Cikls tiek uzskatīts par pilnīgu, ja ir elements, kas ir mazāks vai vienāds ar bāzes vērtību. Tas ir, indeksa vērtība ir salīdzināta un samazinās. Kreisajā pusē darbs tiek pabeigts, kad tiek atrasta lielāka vai vienāda vērtība. Un šeit salīdzināšanas vērtība palielinās.
Šajā sadalīšanas algoritma stadijākas satur ātru šķirošanu, var rasties divas situācijas. Pirmais ir tas, ka rādītājs pa kreisi būs mazāks par labo. Tas norāda kļūdu, tas ir, vienumi, kuriem tas bija norādīts, sarakstā ir nepareizā secībā. Izeja ir vietu maiņa. Otrā situācija ir tad, kad abas slejas ir vienādas vai šķērsotas. Tas norāda uz sekmīgu saraksta atdalīšanu, tas ir, darbu var uzskatīt par pabeigtu.
