Sorteerumismeetodeid

Sorteerumismeetodeid kasutatakse andmete või objektide järjestamiseks kindlaksmääratud järjekorda. Erinevad meetodid pakuvad erinevaid kompromisse aja ja ruumi keerukuse osas. Üks lihtsamaid meetodeid on mullisort (bubble sort), mis korduvate läbimistega võrdleb külgnevaid elemente ja vahetab neid, kui nad on vales järjekorras. Kuigi see on intuitiivne, on selle aja keerukus O(n^2), mis teeb selle suurte andmehulkade puhul ebaefektiivseks. Valiksordil (selection sort) on sarnane aja keerukus, kuid see töötab, leides igal sammul minimaalse (või maksimaalse) elemendi järelejäänud sordimata osast ja asetades selle õigesse kohta.

Kiirsort (quicksort) on populaarne rekursiivne algoritm, mis kasutab "jagude ja valitsemise" strateegiat. See valib elemendi "pivotelemendiks" ja jaotab ülejäänud elemendid nii, et kõik, mis on väiksemad, on pöördelemendist vasakul, ja kõik, mis on suuremad, on paremal. Seejärel rakendab see rekursiivselt ennast kahele alamskaalale. Keskmiselt on kiirsort väga tõhus aja keerukusega O(n log n), kuid halvim juhul võib see olla O(n^2). Mergesort on teine jagude ja valitsemise algoritm, mis jagab andmestiku korduvalt kaheks, sorteerib need ja seejärel ühendab sorteeritud alamskaalad. Selle aja keerukus on alati O(n log n), muutes selle ennustatavamaks.

Insertionsort on tõhus väikeste või peaaegu sorteeritud andmehulkade puhul. See ehitab lõplikult sorteeritud massiivi üks element korraga, asetades iga uue elemendi õigele kohale juba sorteeritud osasse. Selle aja keerukus on keskmiselt O(n^2), kuid O(n) parimal juhul. Hübriidsordid, nagu Timsort (kasutatud Pythonis) ja Introsort (kasutatud C++ STL-is), kombineerivad erinevate algoritmide eeliseid, et saavutada hea jõudlus erinevates stsenaariumites.