Innholdsfortegnelse[Gjemme seg][Forestilling]
Datavitenskap handler om å forstå kompleksiteten til algoritmer og datastrukturer.
Du har en liste over elementer som må sorteres, men du har ikke tid eller ressurser til å bruke en mer kompleks sorteringsalgoritme.
Innsettingssortering er en av de enkleste sorteringsalgoritmene, men den kan være treg for store lister.
Enkel implementering og forståelse har gjort denne metoden til en favoritt blant programmerere. Den er perfekt for små lister eller når du trenger en rask løsning.
I dette blogginnlegget skal vi se på tidskompleksiteten til innsettingssortering. Denne algoritmen brukes til å sortere arrays, og den har en kjøretid på O(n2). Dette betyr at tidskompleksiteten øker med størrelsen på matrisen.
Imidlertid kan denne algoritmen ofte være raskere enn andre sorteringsalgoritmer, for eksempel quicksort.
La oss se nærmere på hvordan innstikkssortering fungerer!
Hva er Insertion Sort Algorithm?
Ett element om gangen, innsettingssortering genererer en sorterbar matrise, som ofte kalles en liste.
For eksempel brukes sortering i kompliserte dataprogrammer som kompilatorer, hvor rekkefølgen på tokens er viktig for tolkningen av programmet.
Hvordan fungerer innsettingssortering?
Når vi bruker innsettingssortering for å sortere en matrise, starter algoritmen med å finne det minste elementet i listen og sette det inn i riktig posisjon.
Den finner deretter den nest minste gjenstanden og setter den inn i riktig posisjon, og så videre.
Algoritmen fungerer ved å gå gjennom listen og sammenligne hvert element med det som kommer før det.
Hvis elementene er i feil rekkefølge, bytter algoritmen dem. Den sjekker deretter om listen er sortert, og hvis den er det, avsluttes algoritmen.
I praksis implementeres innsettingssortering ofte ved å bruke noen få linjer med kode, noe som gjør det til et populært valg for sortering av små matriser. Imidlertid bør tidskompleksitet vurderes når du bruker denne algoritmen.
Eksempel:
Her er et eksempel på hvordan innsettingssortering fungerer. Vi vil bruke følgende array:
1, 2, 3, 4, 5, 6
Algoritmen starter med å finne det minste elementet i listen, som er 1. Den setter det så inn i riktig posisjon, den første posisjonen. Den finner så den nest minste gjenstanden, som er 2. Den setter den inn i riktig posisjon, som er den andre posisjonen.
Den finner så den nest minste gjenstanden, som er 3. Den setter den inn i riktig posisjon, som er den tredje posisjonen.
Den finner så den nest minste gjenstanden, som er 4. Den setter den inn i riktig posisjon, som er den fjerde posisjonen, og så videre. Listen er nå sortert!
Vi kan se fra eksemplet at algoritmen tar seks sammenligninger og bytter for å sortere listen. Dette er fordi det tar n2 sammenligninger og bytte for å sortere en liste med n elementer. I dette tilfellet er n=6.
Hvordan forbedre innsettingssorteringstidskompleksiteten?
Mens innsettingssortering har en kjøretid på O(n2), kan den forbedres ved å bruke en bedre sorteringsalgoritme, for eksempel quicksort.
Quicksort har en O(n log n) kjøretid, som er mye raskere enn O(n2).
Men i noen tilfeller kan innsettingssortering være raskere enn quicksort.
For eksempel, hvis listen allerede er i orden, vil innsettingssortering ta kortere tid enn quicksort.
I praksis blir innsettingssortering ofte implementert ved å bruke noen få linjer med kode, noe som gjør det til et populært valg for sortering av små matriser.
Tidskompleksitet bør imidlertid vurderes når du bruker denne algoritmen.
Tidskompleksiteter
Worst Case Complexity O(n2):
Tidskompleksiteten øker med størrelsen på matrisen. Det tar n2 sammenligninger og bytte for å sortere en liste med n elementer.
For eksempel, hvis vi har en matrise med størrelse 1000, vil algoritmen ta 1,000,000 sammenligninger og bytte for å sortere matrisen.
Best case kompleksitet O(n):
Tidskompleksiteten er den samme som størrelsen på inngangsmatrisen. Jeg
t tar n sammenligninger og bytter for å sortere en liste med n elementer. Tenk for eksempel på en matrise med størrelse 5. Algoritmen vil ta fem sammenligninger og bytte for å sortere matrisen.
Gjennomsnittlig kasuskompleksitet O(n2):
Tidskompleksiteten er mellom verste og beste sakskompleksitet i dette tilfellet.
Det tar n2 sammenligninger og bytte for å sortere en liste med n elementer.
Dermed er innsettingssortering en stabil sorteringsalgoritme.
Hvorfor er innsettingssortering stabil?
Innsettingssortering er stabil fordi den bevarer rekkefølgen av like elementer i inndatamatrisen.
Dette er viktig for mange applikasjoner, som for eksempel datainnhenting eller økonomisk analyse. For eksempel, hvis vi har to lister med tall og ønsker å sammenligne dem, må vi sørge for at rekkefølgen på elementene er bevart.
Hvis listene ikke er sortert, vil vi ikke sammenligne dem nøyaktig.
Legg igjen en kommentar