Võrdlussorteerimisalgoritmide

Võrdlussorteerimisalgoritmid on algoritmide klass, mis sorteerivad järjestust, võrreldes elemente üksteisega. Kõik need algoritmid põhinevad võrdlustegevusel, kus otsustatakse kahe elemendi omavaheline suhe (nt väiksem, suurem või võrdne). Nende efektiivsust mõõdetakse tavaliselt võrdluste arvu järgi, mis on vajalik järjestuse täielikuks sorteerimiseks.

Tuntuimate võrdlussorteerimisalgoritmide hulka kuuluvad mullsorteering, valiksorteering ja sisestussorteering. Need on lihtsad mõista ja rakendada, kuid nende ajaline keerukus on üldjuhul O(n^2), mis muudab nad vähem tõhusaks suurte andmehulkade korral. Kiiremad võrdlussorteerimisalgoritmid, nagu kiiresorteering (quicksort) ja liitsorteering (mergesort), kasutavad sageli jagades ja valitse (divide and conquer) strateegiat, saavutades keskmiselt O(n log n) ajaline keerukus.

Teoreetiline alumine piir võrdlussorteerimisalgoritmide jaoks on O(n log n) võrdlust. See tähendab, et ükski võrdlusmeetodil põhinev algoritm ei saa paremat keskmist või halvimat ajalist keerukust saavutada. Samas on olemas ka mitte-võrdlus sorteerimisalgoritmid, nagu loendus sorteering (counting sort) või radikssorteering (radix sort), mis võivad teatud tingimustel olla kiiremad, kuid nad ei põhine elementide omavahelisel võrdlemisel. Võrdlussorteerimisalgoritmid on fundamentaalsed arvutiteaduses ja neid kasutatakse paljudes erinevates rakendustes, alates andmebaasidest kuni operatsioonisüsteemideni.