Algoritmat e renditjes

Në shkencën kompjuterike, një algoritëm renditje është një algoritëm që vendos elementet e një liste në një rend. Rendet më të përdorura janë rendi numerik dhe rendi leksikografik, si rritës ose zbritës. Renditja efikase është e rëndësishme për optimizimin e efikasitetit të algoritmeve të tjera (të tilla si algoritmet e kërkimit dhe shkrirjes) të cilët kërkojnë që të dhënat hyrëse të jenë në lista të renditura. Renditja është gjithashtu shpesh e dobishme për kaJoniizimin e të dhënave dhe për prodhimin e rezultateve të lexueshme nga njeriu.

Formalisht, dalja e çdo algoritmi klasifikimi duhet të plotësojë dy kushte:

 Prodhimi është në rend moJotonik (çdo element nuk është më i vogël/më i madh se elementi i mëparshëm, sipas rendit të kërkuar).
 Dalja është një ndërrim (një rirenditje, por duke mbajtur të gjithë elementët origjinalë) të hyrjes.

Për efikasitet optimal, të dhënat hyrëse duhet të ruhen në një strukturë të dhënash e cila lejon qasje (akses) të rastësishme dhe jo në atë që lejon vetëm qasje (akses) sekuenciale .

 Historia dhe konceptet 
Që nga fillimi i llogaritjes, problemi i renditjes ka tërhequr një pjesë të madhe të kërkimit, ndoshta për shkak të kompleksitetit të zgjidhjes së tij në mënyrë efikase, pavarësisht deklaratës së tij të thjeshtë dhe të njohur. Ndër autorët e algoritmeve të hershme të renditjes rreth vitit 1951 ishte Betty Holberton, e cila punoi në ENIAC dhe UNIVAC .   Bubble sort u analizua që në vitin 1956.  Algoritmet asimptotike optimale janë njohur që nga mesi i shekullit të 20-tëalgoritme të reja janë ende duke u shpikur, me Timsort të përdorur gjerësisht që daton në 2002, dhe library sort u botua për herë të parë në 2006.

Algoritmet krahasuese të renditjes kanë një kërkesë themelore të krahasimeve Ω( <i id="mwMg">n</i> log <i id="mwMw">n</i> ) (disa sekuenca hyrëse do të kërkojnë një shumëfish n log n krahasimesh, ku n është numri i elementeve në grup që do të renditen). Algoritmet që nuk bazohen në krahasime, si p.sh. countin sort, mund të kenë performancë më të mirë.

Algoritmet e renditjes janë të përhapura në klasat hyrëse të shkencave kompjuterike, ku bollëku i algoritmeve për problemin ofron një hyrje të butë në një sërë konceptesh thelbësore të algoritmeve, të tilla si shënimi i O-së së madhe, algoritmet përça dhe sundo, strukturat e të dhënave si mullarët dhe pemët binare, algoritmet e rastëzuar, analiza e rasteve më të mira, më të këqija dhe mesatare, shkëmbimet kohë-hapësirë dhe kufijtë e sipërm dhe të poshtëm .

 Renditjet e krahasimeve 
Më poshtë është një tabelë e renditjeve të krahasimit . Një renditje krahasimi nuk mund të performojë (mesatarisht) më mirë se . 
+Comparison sortsEmriMë e miraMesatarishtMë e keqeKujtesaI qëndrueshëmMetodaShënime të tjeraIn-place merge sort——PoShkrirjaMund të implementohet si një renditje e qëndrueshme e bazuar në shkrirjen e qëndrueshme në vend.HeapsortJoPërzgjedhjaIntrosortJoParticioni dhe PërzgjedhjaE përdorur në disa implementime tëSTL.Merge sortPoShkrirjaTejet e paralelizueshme (deri në  duke përdorur Algoritmin e Tre Hungarezëve).Tournament sortJoPërzgjedhjaVariacion i Heapsort.Tree sortPoFutjaKur përdoret një pemë kërkimi binare vetë-baraspeshuese.Block sortPoFutja & ShkrirjaSmoothsortJoPërzgjedhjaAn adaptive variant of heapsort based upon the Leonardo sequence rather than a traditional binary heap.TimsortPoFutja & ShkrirjaBën n-1 krahasime kur të dhënat janë tashmë të renditura mbrapsht.Patience sortingJoFutja & PërzgjedhjaGjen të gjitha nënsekuencat më të gjata rritëse në .CubesortPoFutjaMakes n-1 comparisons when the data is already sorted or reverse sorted.QuicksortJoParticionimiQuicksort bëhet zakonisht pa lëvizje me hapësirë sitve.Library sortJoFutjaE ngjashme me një Insertionsort me hendek. Kërkon përkëmbim të rastësishëm të hyrjeve për të hetuar me kufij kohorë me probabilitet të lartë, që e bën Jot të qëndrueshme.ShellsortJoFutjaMadhësi e vogël kodi.Comb sortJoShkëmbimiMesatarisht më e shpejtë se bubble sort.Futja sortPoFutja,në rastin më të keq mbi sekuenca që kanë d inversione.Bubble sortPoShkëmbimiMadhësi kodi e vockël.Cocktail shaker sortPoShkëmbimiNjë variant i bubble sort që adreson rastin e vlerave shumë të vogla në fund të vektoritGJome sortPoShkëmbimiMadhësi e vogël kodi.Odd–even sortPoShkëmbimiMund të ekzekutohet lehtësisht në procesorë në paralel.Simple pancake sortJoPërzgjedhjaNjë lloj i Selection sort.Strand sortPoPërzgjedhjaPërzgjedhja sortJoPërzgjedhjaStabël me  hapësirë shtesë, duke përdorur lista të lidhura, ose kur bëhet si një variant i  Insertion Sort në vend të shkëmbimit të dy mjeteve.Exchange sortJoShkëmbimiTiny code size.Cycle sortJoPërzgjedhjaNë vend me një numër optimal shkrimesh

 Algoritmet popullore të renditjes 
Ndërsa ka një numër të madh të algoritmeve të renditjes, në zbatimet praktike mbizotërojnë disa algoritme. Insertion sort përdoret gjerësisht për grupe të vogla të dhënash, ndërsa për grupe të mëdha të dhënash përdoret një renditje asimptotike efikase, kryesisht heapsort, merge sort ose quicksort. Implementimet efikase zakonisht përdorin një algoritëm hibrid, duke kombinuar një algoritëm asimptotikisht efikas për renditjen e përgjithshme me insertion sort për listat e vogla në fund të një rekursioni. Implementimet shumë të akorduara përdorin variante më të sofistikuara, të tilla si Timsort (merge sort, insertion sort dhe logjikë shtesë), të përdorura në Android, Java dhe Python, dhe introsort (quicksort dhe heapsort), i përdorur (në forma variante) në disa renditje C++ implementimet dhe në . NET .