Quicksort si një metodë programimi

Në vitin 1960, K. A. Hoar zhvilluar një metodë për klasifikim e shpejtë të informacionit, u bë më i famshëm. Sot ajo është përdorur gjerësisht në programimin, pasi ajo ka një shumë të pronave pozitive: ajo mund të përdoret për rastet e përgjithshme, kjo kërkon një rritje të vogël në memorien shtesë, në përputhje me lloje të ndryshme të listave dhe të lehtë për të zbatuar. Por ka të meta, i cili ka Quicksort: duke përdorur punën e lejuar shumë gabime, dhe kjo është disi e paqëndrueshme.

Megjithatë, kjo është versioni më i studiuar. Pas Hoare pagesës së parë, shumë të bëjë studimin e saj të dendur. bazë të madhe është themeluar në çështjet teorike të gjetur koha e kaluar në punë, e cila mbështetet nga prova empirike. Ka pasur propozime reale për të përmirësuar algorithm themelore dhe rritjen e shpejtësisë.

Quicksort është shumë e zakonshme, ajo mund të gjendet kudo. Në bazë të saj metodë është zbatuar TList.Sort, i pranishëm në të gjitha versionet (me përjashtim 1) Delphi, funksionin e bibliotekës të kohës që u desh për të përfunduar, qsort në C ++.

Parimi bazë i funksionimit mund të formulohet si një "përça dhe sundo". Kjo ndodh thyer listën në dy grupe dhe janë të renditura për secilën pjesë në vetvete. Ai vijon se më shumë vëmendje duhet t'i kushtohet procesit të ndarjes, gjatë së cilës këto ndodh: përcaktohet nga një element bazë dhe relativisht ka riorganizohet listën e tij të gjithë. E ndërtuar në të majtë të një grupi të kandidatëve, vlera e të cilave është më pak se të gjitha rregullat e tjera të transferimit. Ajo rezulton se elementi kryesor në listën e renditura është në vendin që i takon. Faza tjetër - një sfidë gjithkund rekursive funksionon klasifikim për të dy anët e elementeve relative në bazë. Ajo përfundon procesi funksionon vetëm në qoftë se lista përmban vetëm një element, që do të zgjidhet. Kështu, në mënyrë për të zotëruar një funksion programimi si një lloj të shpejtë, është e nevojshme të dinë punën e algoritme të nivelit më të ulët: a) zgjedhja e anëtarit bazë; b) një listë e ndërrim më efektive për të prodhuar dy grupe me vlera më të vogla dhe më të mëdha.

Njoh nga afër me parimet e parë. Kur zgjedh anëtarin bazë, në mënyrë ideale duhet të zgjidhen nga lista e mesatare. Pastaj në pushim është i ndarë në dy gjysma të barabarta. Vetëm llogaritur vlera mesatare në listë është shumë e vështirë, kështu që edhe më të shpejtë sorting anashkalon këtë anë gur. Por zgjedhja e elementit bazë me vlerën maksimale apo minimale - gjithashtu nuk opsioni më i mirë. Në rast përcaktim i tillë i një krijon listat bosh do të jetë e garantuar, dhe e dyta të plotë. Prandaj konkluzioni që si anëtar bazë duhet të jenë të zgjedhur një që është më afër me mesataren, por në maksimum dhe minimum.

Pasi një zgjedhje është e vendosur, ju mund të vazhdojë për të algorithm dekompozim. Kjo ashtuquajtura sythe Inner lloj të shpejtë. Çdo gjë është ndërtuar mbi dy indekseve të Shpejtë Access: së pari shkojnë mbi elementet nga e majta në të djathtë, të dytë, në të kundërtën, nga djathta në të majtë. Fillon të drejtën e ekzekutimit operacion: indeksi është në listë dhe krahasuar të gjitha vlerat për të kryesore. Cikli është i plotë kur elementi është më pak se ose e barabartë me bazë. Kjo është, nuk është një krahasim dhe ul vlerën e indeksit. Në anën e majtë, kur puna është e përfunduar më e madhe se ose vlerë të barabartë. Këtu, rritet vlera krahasimi.

Në këtë fazë të algoritmi ndarjes i cili përfshin Quicksort, dy situata mund të lindin. E para është se indeksi në të majtë është më pak se e drejtë. Kjo tregon një gabim, atëherë ka elemente në të cilën është deklaruar në listë janë në mënyrë të gabuar. Output - ndryshojnë vendet e tyre. Situata e dytë është kur të dy i kolonës është e barabartë ose kaluar. Kjo tregon një ndarje të suksesshëm të listës, që është, puna tani është kompletuar.