Pikalajittelu on erittäin tehokas lajittelualgoritmi, joka perustuu tietojoukon osiointiin pienempiin matriiseihin. Suuri matriisi jaetaan kahteen ryhmään, joista yhdessä on määritettyä arvoa pienempiä arvoja, eli pivot, jonka perusteella osio tehdään, ja toisessa taulukossa arvot, jotka ovat suurempia kuin pivot-arvo.
Quicksort-osiot an taulukkoa ja kutsuu sitten itseään rekursiivisesti kahdesti saadun kahden alialueen lajittelemiseksi. Tämä algoritmi on varsin tehokas suurikokoisille tietojoukoille, koska sen keskimääräinen ja pahimmassa tapauksessa monimutkaisuus on O (n2).
Osio pikalajittelussa
Seuraavan animaation esitys selittää, miten löytää taulukon pivot-arvo.
Pivot-arvo jakaa luettelon kahteen osaan. Ja rekursiivisesti löydämme jokaisen alaluettelon pivotin, kunnes kaikki luettelot sisältävät vain yhden elementin.
Pikalajittelun pivot-algoritmi
Perustuen ymmärrykseen osioinnista pikalajittelussa, yritä nyt kirjoittaa sille algoritmi, joka on seuraava:
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Pikalajittelun pivot-pseudokoodi
Yllä olevan algoritmin pseudokoodi voidaan johtaa –
Pikalajittelualgoritmi
Pivot-algoritmia käyttämällä rekursiivisesti päädytään pienempiin mahdollisiin osioihin. Jokainen osio käsitellään sitten nopeaa lajittelua varten. Määritämme rekursiivisen algoritmin pikalajikkeelle seuraavasti –
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Pikalajittelun pseudokoodi
Jos haluat saada siihen enemmän, katso pseudokoodi nopeasti lajittelualgoritmi –
Jos haluat tietää nopeasta lajittelusta C-ohjelmointikielellä, napsauta tätä.