Hurtigsortering som programmering metode

I 1960, K. A. Hoar udviklet en metode til hurtig sortering af information, blev den mest berømte. I dag er det meget udbredt i programmering, da det har en masse positive egenskaber: det kan bruges til generelle sager, det kræver en lille stigning i den ekstra hukommelse, kompatibelt med forskellige typer af lister og let at implementere. Men der er ulemper, som har hurtigsortering: hjælp arbejde tillod en masse fejl, og det er noget ustabil.

Men det er den mest studerede version. Efter den første betaling Hoare, mange gør dens tætte undersøgelse. stor base blev etableret den teoretiske spørgsmål om at finde den tid, der bruges på jobbet, som underbygges af empiriske beviser. Der var virkelige forslag til forbedring af grundlæggende algoritme og øget hastighed.

Hurtigsortering er meget almindeligt, det kan findes overalt. På grundlag heraf fremgangsmåden er implementeret TList.Sort, til stede i alle versioner (undtagen 1) Delphi, biblioteket funktion af tid, det tog at fuldføre, qsort i C ++.

Det grundlæggende princip i drift kan formuleres som en "del og erobring". Det sker at bryde listen i to grupper, og er sorteret til hver del af sig selv. Heraf følger, at mere bør man være opmærksom på adskillelsen proces, hvorunder sker følgende: bestemmes af en base element og har relativt omstruktureret hele hans liste. Bygget til venstre for en gruppe af kandidater, hvis værdi er mindre end alle de andre regler om transfer. Det viser sig, at det vigtigste element i ordnet liste er i sin retmæssige plads. Den næste fase - en tackling rekursive sorterings- funktioner til begge sider af elementerne i forhold til basen. Det ender processen fungerer kun, hvis listen kun indeholder et element, der skal sorteres. For at beherske en programmering funktion som en hurtig slags, er det nødvendigt at kende arbejdet i lavere niveau algoritmer: a) valg af det faste element; b) en liste over de mest effektive permutation til at producere to sæt med mindre og større værdier.

Gør med første principper. Når du vælger grundelementet, bør ideelt være valgt fra listen over gennemsnittet. Så på pause er delt i to lige store halvdele. Bare beregne gennemsnitlige værdi i listen er meget vanskeligt, så selv den hurtigste sortering uden om dette calculus side. Men valget af det grundlæggende element med den maksimale eller minimale værdi - også ikke den bedste løsning. Såfremt sådanne bestemmelse af en skaber, vil være garanteret tomme lister, og det andet hele. Derfor er konklusionen, at som basisdelen bør vælges en, der er tættere på gennemsnittet, men på den maksimale og minimale.

Når et valg er bestemt, kan du fortsætte til nedbrydning algoritme. Denne såkaldte indre løkker hurtig slags. Alt er bygget på to hurtig adgang indekser: først gå over elementerne fra venstre mod højre, den anden, tværtimod, fra højre til venstre. Begynder drift udførelse højre: indekset er på listen og sammenligne alle værdier til de vigtigste. Cyklussen er afsluttet, når elementet er mindre end eller lig med grundlinjen. Det er, er der en sammenligning og reducerer værdien af indekset. På venstre hånd, når arbejdet er færdigt større end eller lig værdi. Her, de sammenligning værdi stiger.

På dette stadium af partitionering algoritme, som omfatter hurtigsortering, kan der opstå to situationer. Den første er, at indekset til venstre er mindre end højre. Dette indikerer en fejl, så er der elementer, som det blev anført i listen er i den forkerte rækkefølge. Output - ændre deres pladser. Den anden situation er, når begge af søjlen er lig med eller krydses. Dette indikerer en vellykket adskillelse af listen, det vil sige, at arbejdet er nu færdig.