Algoritmat e renditjes

[djathtas|parapamje| [Merge sort]]
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 Ω(  log  ) (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 . 

## 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 .