Quicksort
Quicksort on lajittelualgoritmi, jota käytetään joukon elementtien lajitteluun. Sen loi Tony Hoare vuonna 1959, ja sitä käytetään edelleen laajalti. Quicksort-algoritmi luo osioita matriisiin, mikä tarkoittaa sitä, että se jakaa matriisin kahteen osaan ja jatkaa sitten näiden osien jakamista useampiin osiin ja lajittelua matkan varrella. Se tekee varsinaisen lajittelun, koska se on luonteeltaan vertailulajittelu. Tämä tarkoittaa sitä, että se valitsee sarjan keskipisteen ja vertaa sitä sitten kaikkiin muihin sarjan pisteisiin.
Animoitu visualisointi quicksort-algoritmista. Vaakasuorat viivat ovat pivot-arvoja
Algoritmi
- Valitse mikä tahansa elementti joukosta, tämä on nyt nivelpiste.
- Jaottele elementit. Vertaile kaikkia matriisin elementtejä nivelpisteeseen, nivelpistettä alempana olevat elementit siirretään nivelpisteen vasemmalle puolelle ja kaikki nivelpistettä ylempänä olevat matriisin elementit siirretään nivelpisteen oikealle puolelle. Huomaa, että pivot on nyt lajitellussa asennossaan.
- Etsi uudelleen kaksi osiota. Sovelletaan edellä mainittuja kahta vaihetta vaiheessa 2 luotuihin kahteen osioon.
Usein niveleksi valitaan vasemmanpuoleisin elementti. Rekursio tarkoittaa, että algoritmi suorittaa täsmälleen saman algoritmin kahdelle osiolle, jotka on luotu vertailemalla pivot-elementtiin. Huomaa, että tämä algoritmi jatkaa matriisin jakamista osajoukkoihin ja näiden osajoukkojen jakamista vielä pienempiin osajoukkoihin. Joka kerta kun se tekee näin, se valitsee uuden pivot-arvon alajoukon sisällä ja vertaa elementtejä alajoukkoon. Perustapaus on, kun algoritmi saavuttaa alaruudun, jossa on vain yksi elementti, jolloin se vain pysähtyy, koska yhtä elementtiä ei tarvitse lajitella.
