Sorteringsalgoritmer forklaret
Sorteringsalgoritmer er et sæt instruktioner, der tager en matrix eller liste som input og arrangerer elementerne i en bestemt rækkefølge.
Sorter er oftest i numerisk rækkefølge eller i form af alfabetisk rækkefølge (kaldet leksikografisk) og kan være i stigende rækkefølge (AZ, 0-9) eller faldende (ZA, 9-0) rækkefølge.
Hvorfor sorteringsalgoritmer er vigtige
Da sortering ofte kan reducere kompleksiteten af et problem, er det en vigtig algoritme inden for datalogi. Disse algoritmer har direkte applikationer til at søge algoritmer, databasealgoritmer, opdele og erobre metoder, datastrukturalgoritmer og mange flere.
Nogle almindelige sorteringsalgoritmer
Nogle af de mest almindelige sorteringsalgoritmer er:
- Valg af sortering
- Boblesortering
- Indsats sortering
- Flet sortering
- Hurtig sortering
- Heap Sort
- Tællesortering
- Radix Sort
- Bucket Sort
Klassificering af sorteringsalgoritme
Sorteringsalgoritmer kan kategoriseres ud fra følgende parametre:
- Baseret på antal swaps eller inversion Dette er antallet af gange, algoritmen bytter elementer for at sortere input.
Selection Sort
kræver det mindste antal swaps. - Baseret på antal sammenligninger Dette er antallet af gange, algoritmen sammenligner elementer for at sortere input. Ved hjælp af Big-O-notering kræver sorteringsalgoritmeeksemplerne, der er anført ovenfor, mindst
O(nlogn)
sammenligninger i bedste fald ogO(n^2)
sammenligninger i værste fald for de fleste output. - Baseret på rekursion eller ikke-rekursion Nogle sorteringsalgoritmer, f.eks.
Quick Sort
, Bruger rekursive teknikker til at sortere input. Andre sorteringsalgoritmer, såsomSelection Sort
ellerInsertion Sort
, bruger ikke-rekursive teknikker. Endelig bruger en eller anden sorteringsalgoritme, såsomMerge Sort
både rekursive såvel som ikke-rekursive teknikker til at sortere input. - Baseret på stabilitetssortering siges algoritmer at være,
stable
hvis algoritmen opretholder den relative rækkefølge af elementer med lige nøgler. Med andre ord forbliver to ækvivalente elementer i samme rækkefølge i det sorterede output, som de var i input. Insertion sort
,Merge Sort
ogBubble Sort
er stabileHeap Sort
ogQuick Sort
er ikke stabile- Baseret på ekstra pladsbehov siges det at sorteringsalgoritmer er,
in place
hvis de kræver konstantO(1)
ekstra plads til sortering. Insertion sort
ogQuick-sort
erin place
sorteret, når vi flytter elementerne omkring drejetappen og faktisk ikke bruger et separat array, hvilket IKKE er tilfældet i flettsortering, hvor størrelsen på inputet skal tildeles på forhånd for at gemme output under sorteringen.Merge Sort
er etout place
slags eksempel, da det kræver ekstra hukommelsesplads til dets operationer.
Bedst mulig tidskompleksitet til enhver sammenligningsbaseret sortering
Enhver sammenligningsbaseret sorteringsalgoritme skal foretage mindst nLog2n-sammenligninger for at sortere input-arrayet, og Heapsort og merge-sortering er asymptotisk optimale sammenligningssorteringer. Dette kan let bevises ved at tegne beslutningstrædiagrammet.