Võrdlussorteerimisalgoritmid

Võrdlussorteerimisalgoritmid on algoritmide klass, mis sorteerivad järjestusi, võrreldes elemente. Need algoritmid kasutavad järjestuse elementide vahelise järjestuse määramiseks ainult võrdlusoperatsioone. Tuntumate võrdlussorteerimisalgoritmide hulka kuuluvad mullsorteerimine, valiksorteerimine, sisestussorteerimine, kiire sorteerimine ja ühinemissorteerimine.

Mullsorteerimine on lihtne algoritm, mis korduvate läbimistega järjestuses, võrreldes külgnevaid elemente ja vahetades neid, kui nad on vales järjekorras. Valiksorteerimine jagab järjestuse kaheks osaks: sorteeritud ja sorteerimata. See leiab sorteerimata osast väikseima elemendi ja asetab selle sorteeritud osa lõppu. Sisestussorteerimine ehitab lõppjärjestuse element element haaval, võttes iga elemendi sorteerimata osast ja asetades selle õigesse kohta sorteeritud osas.

Kiire sorteerimine on efektiivne algoritm, mis kasutab "jagude ja valitsemise" strateegiat. See valib järjestusest "pivotelemendi" ja jagab teised elemendid kaheks alamsiinuseks: need, mis on väiksemad kui pivot, ja need, mis on suuremad. Seejärel rakendab algoritm ennast rekursiivselt nendele alamsiinustele. Ühinemissorteerimine on samuti "jagude ja valitsemise" algoritm, mis jagab järjestuse rekursiivselt väiksemateks osadeks, sorteerib need ja seejärel ühendab need sorteeritud osad lõpuks ühtseks sorteeritud järjestuseks.

Võrdlussorteerimisalgoritmide teoreetiline alumine piir on O(n log n), mis tähendab, et neid ei saa olla parem kui lineaarselt logaritmiline, kus n on järjestuse elementide arv.