Quicksort as 'n ontwikkeling metode

In 1960, K. A. grys ontwikkel 'n metode vir die vinnige sortering van inligting, is die mees bekende. Vandag is dit is wyd gebruik word in programmering, aangesien dit 'n baie positiewe eienskappe: dit kan gebruik word vir algemene sake, dit vereis 'n klein toename in die addisionele geheue, versoenbaar is met verskillende tipes van lyste en maklik om te implementeer. Maar daar is nadele, wat het Quicksort: die gebruik van die werk toegelaat om 'n klomp van foute, en dit is 'n bietjie onstabiel.

Dit is egter die meeste bestudeer weergawe. Na afloop van die eerste betaling Hoare, baie doen sy digte studie. groot basis is gestig op teoretiese vrae van die vind van die tyd spandeer op die baan, wat ondersteun word deur empiriese bewyse. Daar was real voorstelle om die basiese algoritme en 'n verhoogde spoed te verbeter.

Quicksort is baie algemeen, dit kan oral gevind word. Op sy basis die metode toegepas word TList.Sort, teenwoordig in al die weergawes (behalwe 1) Delphi, die biblioteek funksie van tyd wat dit neem om te voltooi, qsort in C ++.

Die basiese beginsel van werking kan geformuleer word as 'n "Verdeel en oorwin". Dit kom breek die lys in twee groepe en word gesorteer vir elke deel vanself. Dit volg dus dat meer aandag geskenk moet word aan die skeidingsproses, waartydens die volgende plaasvind: word bepaal deur 'n basis element en het relatief herrangskik sy hele lys. Gebou aan die linkerkant van 'n groep van kandidate, waarvan die waarde minder as al die ander oordrag reëls. Dit blyk dat die belangrikste element in die gesorteerde lys is in sy regmatige plek. Die volgende fase - 'n uitdaging rekursiewe sorteer funksies vir beide kante van die elemente met betrekking tot die basis. Dit eindig die proses werk net as die lys bevat slegs een element, wat word gesorteer. Dus, ten einde 'n programmering funksie as 'n vinnige soort bemeester, is dit nodig om die werk van 'n laer vlak algoritmes weet: a) die keuse van die base lid; b) 'n lys van die mees doeltreffende permutasie om twee stelle met kleiner en groter waardes produseer.

Vertroud te maak met die eerste beginsels. By die keuse van die base lid, ideaal moet gekies word uit die lys van gemiddelde. Dan op die breek is verdeel in twee gelyke helftes. Net bereken die gemiddelde waarde in die lys is baie moeilik, so selfs die vinnigste sorteer verbypaaie hierdie analise kant. Maar die keuse van die basiese element met die maksimum of minimum waarde - ook nie die beste opsie. In geval so 'n bepaling van 'n skep leë lyste sal gewaarborg word, en die tweede vol. Vandaar die gevolgtrekking gekom dat as die basis lid een wat nader aan die gemiddelde moet gekies word, maar op die maksimum en minimum.

Sodra 'n keuse word bepaal, kan jy voortgaan om die ontbinding algoritme. Hierdie sogenaamde innerlike sirkelroetes vinnige soort. Alles is gebou op twee Rapid Access indekse: eerste gaan oor die elemente van links na regs, die tweede nie, inteendeel, van regs na links. Begin uitvoering operasie reg: die indeks is op die lys en vergelyk al die waardes aan die hoof. Die siklus is voltooi wanneer die element minder as of gelyk aan die basislyn is. Dit is, is daar 'n vergelyking en verlaag die waarde van die indeks. Aan sy linkerhand wanneer die werk klaar is groter as of gelyk waarde. Hier is die vergelyking waarde toeneem.

Op hierdie stadium van skeiding algoritme wat quicksort bestaan, kan twee situasies ontstaan. Die eerste is dat die indeks aan die linkerkant is minder as reg. Dit dui op 'n fout, dan is daar elemente waarop dit gestel in die lys is in die verkeerde volgorde. Uitset - verander hul plekke. Die tweede situasie is wanneer beide van die kolom is gelyk aan of gekruis. Dit dui op 'n suksesvolle skeiding van die lys, dit wil sê die werk is nou afgehandel.