Quicksort som programmeringsmetode

I 1960 K. A. Hoar utviklet en metode for rask sortering av informasjon, ble den mest kjente. I dag er det mye brukt i programmering, som den har mange positive egenskaper: det kan brukes til generelle tilfeller, krever det en liten økning i ekstra minne, kompatibel med ulike typer lister og enkel å implementere. Men det er ulemper, som har Quicksort: ved hjelp av arbeid tillot mye feil, og det er noe ustabil.

Men det er det mest studerte versjonen. Etter den første betalingen Hoare, mange gjør sin tette studien. stor base ble etablert på teoretiske spørsmål om å finne tid brukt på jobben, som er understøttet av empiriske bevis. Det var ekte forslag for å bedre den grunnleggende algoritme og økt hastighet.

Quicksort er svært vanlig, det kan finnes overalt. På sin basis metoden er implementert TList.Sort, finnes i alle versjoner (unntatt en) Delphi, biblioteket funksjon av tiden det tok å fullføre, qsort i C ++.

Grunnprinsippet for drift kan formuleres som en "splitt og erobre". Det oppstår bryte opp listen i to grupper, og er sortert for hver del av seg selv. Det følger av dette at mer oppmerksomhet bør vies til separasjonsprosessen, hvorunder følgende skjer: bestemmes av et basiselement og har forholdsvis omar hele sin liste. Bygget til venstre for en gruppe av kandidater, hvis verdi er mindre enn alle de andre flytteregler. Det viser seg at det viktigste elementet i den sorterte listen er på sin rettmessige plass. Den neste fasen - en duell rekursive sorteringsfunksjoner for begge sider av elementene i forhold til underlaget. Det ender prosessen fungerer bare hvis listen inneholder bare ett element, som skal sorteres. Derfor, for å mestre en programmeringsfunksjon som en rask slag, er det nødvendig å vite arbeidet til lavere nivå algoritmer: a) valg av basisdelen; b) en liste over de mest effektive permutasjon for å fremstille to sett med mindre og større verdier.

Kjent med første prinsipper. Ved valg av basedelen, bør ideelt sett velges fra listen over gjennomsnittet. Deretter på bruddet er delt i to like halvdeler. Bare beregne gjennomsnittsverdien i listen er veldig vanskelig, så selv de raskeste sortering omgår dette kalkulus side. Men valget av den grunnleggende element med maksimums- eller minimumsverdien - heller ikke det beste alternativet. Ved slik fastsettelse av en skaper tomme lister vil bli garantert, og den andre full. Derav den konklusjon at når basisdelen bør velges en som er nærmere gjennomsnittet, men av den maksimale og minimale.

Når et valg er bestemt, kan du gå videre til nedbrytning algoritmen. Denne såkalte indre sløyfer rask slag. Alt er bygget på to rask tilgang indekser: først gå over elementene fra venstre til høyre, den andre, tvert imot, fra høyre til venstre. Begynner oppgaveutføring høyre: indeksen er på listen og sammenligne alle verdiene til hoved. Syklusen er ferdig når elementet er mindre enn eller lik grunnlinjen. Det vil si, det er en sammenligning og reduserer verdien av indeksen. På venstre hånd når arbeidet er ferdig større enn eller lik verdi. Her blir sammenligning verdien øker.

På dette stadium av partisjone algoritme som omfatter Quicksort, kan det oppstå to situasjoner. Den første er at indeksen til venstre er mindre enn høyre. Dette indikerer en feil, så er det elementer som det ble nevnt i listen er i feil rekkefølge. Utgang - endre sine plasser. Den andre situasjonen er når både av kolonnen er lik eller krysset. Dette indikerer en vellykket separasjon av listen, det er, er arbeidet nå fullført.