Quicksort

Quicksort on tõhus sortimisalgoritm, mida kasutatakse peamiselt suurte andmehulkade sortimiseks. See on teatud tüüpi jaga ja valluta algoritm, mis tähendab, et see jagab suure andmekogumi alamhulkadeks, seejärel töötleb iga alamhulka, et sortida kogu andmekogum.

Kiirsortimise algoritmi väljendatakse tavaliselt pseudokoodis:

Kiire sortimine (A, vasak, parem)
kui parem> vasak
vali pöördeväärtus A[pivot]
partitsiooni massiiv pöörde ümber
Kiirsortimine (A, vasak, pivotIndex – 1)
Kiirsortimine (A, pivotIndex +1, parem)

Kiirsortimise algoritmi saab täpsemalt selgitada järgmiselt. Algoritm algab partitsioonielemendina kasutatavast andmekogumist elemendi valimisega, mida nimetatakse pivotiks. Seejärel luuakse pöörde põhjal andmete alamhulgad, kus ühte alamkomplekti asetatakse pöördepunktist väiksemad elemendid ja teise alamkomplekti pivodist suuremad elemendid. Seejärel töötleb algoritm rekursiivselt iga alamhulka, kuni kogu andmekogum on sorteeritud.

Kiirsortimisalgoritm on üks tõhusamaid saadaolevaid sortimisalgoritme, mille keskmine ajaline keerukus on O(N log N). See on eriti kasulik suurte andmekogumite sortimiseks, näiteks andmebaasisüsteemides leiduvate andmete sortimiseks.

Tänu oma tõhususele kasutatakse kiirsortimisalgoritmi paljudes programmeerimiskeeltes, sealhulgas Java, C++ ja Python. Seda kasutatakse sageli ka sellistes rakendustes nagu otsingualgoritmid, graafikatöötlus ja küberturvalisus.