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 . [1] [2] Bubble sort u analizua që në vitin 1956. Algoritmet asimptotike optimale janë njohur që nga mesi i shekullit të 20-tëStampa:Sndalgoritme 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 Stampa:Math. [3]
| Emri | Më e mira | Mesatarisht | Më e keqe | Kujtesa | I qëndrueshëm | Metoda | Shënime të tjera |
|---|---|---|---|---|---|---|---|
| In-place merge sort | — | — | Stampa:Sort | Stampa:Sort | Po | Shkrirja | Mund të implementohet si një renditje e qëndrueshme e bazuar në shkrirjen e qëndrueshme në vend.[4] |
| Heapsort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | |
| Introsort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Particioni dhe Përzgjedhja | E përdorur në disa implementime tëSTL. |
| Merge sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Shkrirja | Tejet e paralelizueshme (deri në Stampa:Math duke përdorur Algoritmin e Tre Hungarezëve). |
| Tournament sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | Variacion i Heapsort. |
| Tree sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Futja | Kur përdoret një pemë kërkimi binare vetë-baraspeshuese. |
| Block sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Futja & Shkrirja | |
| Smoothsort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | An adaptive variant of heapsort based upon the Leonardo sequence rather than a traditional binary heap. |
| Timsort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Futja & Shkrirja | Bën n-1 krahasime kur të dhënat janë tashmë të renditura mbrapsht. |
| Patience sorting | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Futja & Përzgjedhja | Gjen të gjitha nënsekuencat më të gjata rritëse në Stampa:Math. |
| Cubesort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Futja | Makes n-1 comparisons when the data is already sorted or reverse sorted. |
| Quicksort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Particionimi | Quicksort bëhet zakonisht pa lëvizje me hapësirë sitveStampa:Math.[5][6] |
| Library sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Futja | E 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. |
| Shellsort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Futja | Madhësi e vogël kodi. |
| Comb sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Shkëmbimi | Mesatarisht më e shpejtë se bubble sort. |
| Futja sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Futja | Stampa:Math,në rastin më të keq mbi sekuenca që kanë d inversione. |
| Bubble sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Shkëmbimi | Madhësi kodi e vockël. |
| Cocktail shaker sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Shkëmbimi | Një variant i bubble sort që adreson rastin e vlerave shumë të vogla në fund të vektorit |
| GJome sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Shkëmbimi | Madhësi e vogël kodi. |
| Odd–even sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Shkëmbimi | Mund të ekzekutohet lehtësisht në procesorë në paralel. |
| Simple pancake sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | Një lloj i Selection sort. |
| Strand sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Po | Përzgjedhja | |
| Përzgjedhja sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | Stabël me Stampa:Tmath 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.[7] |
| Exchange sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Shkëmbimi | Tiny code size. |
| Cycle sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Stampa:Sort | Jo | Përzgjedhja | Në 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 .