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ë – 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 $O (n log n)$ . ^[3]

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

^ "Meet the 'Refrigerator Ladies' Who Programmed the ENIAC". Mental Floss. 2013-10-13. Arkivuar nga origjinali më 2018-10-08. Marrë më 2016-06-16. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Lohr, Steve (17 dhj 2001). "Frances E. Holberton, 84, Early Computer Programmer". NYTimes. Arkivuar nga origjinali më 16 dhjetor 2014. Marrë më 16 dhjetor 2014. {{cite news}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "8", Introduction To Algorithms (bot. 3rd), Cambridge, MA: The MIT Press, fq. 167, ISBN 978-0-262-03293-3 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Huang, B. C.; Langston, M. A. (dhjetor 1992). "Fast Stable Merging and Sorting in Constant Extra Space". Comput. J. 35 (6): 643–650. CiteSeerX 10.1.1.54.8381. doi:10.1093/comjnl/35.6.643. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Prof. E. Rahm. "Sortierverfahren" (PDF). Dbs.uni-leipzig.de. Arkivuar (PDF) nga origjinali më 23 gusht 2022. Marrë më 1 mars 2022. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Sedgewick, Robert (1 shtator 1998). Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (bot. 3). Pearson Education. ISBN 978-81-317-1291-7. Marrë më 27 nëntor 2012. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857. doi:10.1145/359619.359631. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ "SELECTION SORT (Java, C++) – Algorithms and Data Structures". Algolist.net. Arkivuar nga origjinali më 9 dhjetor 2012. Marrë më 14 prill 2018. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[refrigerator-1] "Meet the 'Refrigerator Ladies' Who Programmed the ENIAC". Mental Floss. 2013-10-13. Arkivuar nga origjinali më 2018-10-08. Marrë më 2016-06-16. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[NYTimes-2] Lohr, Steve (17 dhj 2001). "Frances E. Holberton, 84, Early Computer Programmer". NYTimes. Arkivuar nga origjinali më 16 dhjetor 2014. Marrë më 16 dhjetor 2014. {{cite news}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "8", Introduction To Algorithms (bot. 3rd), Cambridge, MA: The MIT Press, fq. 167, ISBN 978-0-262-03293-3 {{citation}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[4] Huang, B. C.; Langston, M. A. (dhjetor 1992). "Fast Stable Merging and Sorting in Constant Extra Space". Comput. J. 35 (6): 643–650. CiteSeerX 10.1.1.54.8381. doi:10.1093/comjnl/35.6.643. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[5] Prof. E. Rahm. "Sortierverfahren" (PDF). Dbs.uni-leipzig.de. Arkivuar (PDF) nga origjinali më 23 gusht 2022. Marrë më 1 mars 2022. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[6] Sedgewick, Robert (1 shtator 1998). Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (bot. 3). Pearson Education. ISBN 978-81-317-1291-7. Marrë më 27 nëntor 2012. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[sedgewickQsortPaper-7] Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857. doi:10.1145/359619.359631. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[8] "SELECTION SORT (Java, C++) – Algorithms and Data Structures". Algolist.net. Arkivuar nga origjinali më 9 dhjetor 2012. Marrë më 14 prill 2018. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]