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:

  1. Baseret på antal swaps eller inversion Dette er antallet af gange, algoritmen bytter elementer for at sortere input. Selection Sortkræver det mindste antal swaps.
  2. 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 og O(n^2)sammenligninger i værste fald for de fleste output.
  3. Baseret på rekursion eller ikke-rekursion Nogle sorteringsalgoritmer, f.eks. Quick Sort, Bruger rekursive teknikker til at sortere input. Andre sorteringsalgoritmer, såsom Selection Sorteller Insertion Sort, bruger ikke-rekursive teknikker. Endelig bruger en eller anden sorteringsalgoritme, såsom Merge Sortbåde rekursive såvel som ikke-rekursive teknikker til at sortere input.
  4. Baseret på stabilitetssortering siges algoritmer at være, stablehvis 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.
  5. Insertion sort, Merge Sortog Bubble Sorter stabile
  6. Heap Sortog Quick Sorter ikke stabile
  7. Baseret på ekstra pladsbehov siges det at sorteringsalgoritmer er, in placehvis de kræver konstant O(1)ekstra plads til sortering.
  8. Insertion sortog Quick-sorter in placesorteret, 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.
  9. Merge Sorter et out placeslags 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.