Sisällysluettelo:
Määritelmä - mitä Quicksort tarkoittaa?
Quicksort on suosittu lajittelualgoritmi, joka on käytännössä usein nopeampaa kuin muut lajittelualgoritmit. Se hyödyntää jako-ja-valloitus -strategiaa lajittelemaan nopeasti dataelementit jakamalla suuri ryhmä kahteen pienempään taulukkoon. Sen on kehittänyt Charles Antony Richard Hoare (tunnetaan yleisesti nimellä CAR Hoare tai Tony Hoare) vuonna 1960 kansallisen fyysisen laboratorion konekääntämisprojektiksi.Techopedia selittää Quicksortin
Quicksort on algoritmi, jota käytetään lajittelemaan kohteet nopeasti taulukossa riippumatta siitä, kuinka suuri taulukko on. Se on melko skaalautuva ja toimii suhteellisen hyvin pienissä ja suurissa tietojoukkoissa, ja se on helppo toteuttaa pienellä ajan monimutkaisuudella. Se tekee tämän jakamalla ja valloittamalla -menetelmällä, joka jakaa yhden suuren taulukon kahteen pienemmäksi ja toistaa sitten tämän prosessin kaikille luotuille ryhmille, kunnes lajittelu on valmis.
Pikavalintalgoritmi suoritetaan seuraavasti:
- Kääntöpiste valitaan taulukosta.
- Taulukko järjestetään uudelleen siten, että kaikki kääntöpistettä pienemmät arvot siirretään ennen sitä ja kaikki kääntöpistettä suuremmat arvot siirretään sen jälkeen, arvoilla, jotka vastaavat kääntösuuntaa kumpaankin suuntaan. Kun tämä on tehty, nivel on lopullisessa asennossa.
- Yllä oleva vaihe toistetaan jokaiselle pienempien arvojen alaryhmälle, samoin kuin tehdään erikseen suurempien arvojen alaryhmälle.
Tätä toistetaan, kunnes koko taulukko on lajiteltu.
