Denne artikkelen er en del av en serie som dekker sorteringsalgoritmer I JavaScript. Resten av serien finner du her. Hvis du er ny på sorteringsalgoritmer, eller algoritmer generelt, les dette først for å få et solid grunnlag for å gå videre. I dag skal jeg dekke ins og outs av innsetting sortering. Innsetting sortering er mer kompleks, men litt mer nyttig enn boble sortering. Det verste fallet for det ligner på bubble sort, men det beste tilfellet gjør det egnet for tider når du er ganske sikker på at en liste nesten er sortert eller sannsynligvis allerede sortert. La oss få det store bildet.
Innsettingssortering fungerer ved å se på hvert element i en liste (starter med det andre elementet) og sammenligne det med elementet før. Hvis varen før er større, byttes de. Dette fortsetter til elementet er mindre, og vi gjør det samme for det neste elementet i listen.
Innsettingssortering er ikke så ille.. så lenge du bruker den under de rette omstendighetene.
- det er raskere enn De fleste o(n log n) sorteringsalgoritmer for små lister.
- det er ekstremt minne effektiv krever Bare O (1) ekstra plass for enkelt element som blir flyttet.
- det er stabilt-like elementer vises i samme rekkefølge i den sorterte listen.
- det er adaptivt — det er raskt når du sorterer for det meste sorterte lister eller når du legger til elementer i en allerede sortert liste.
- Det er veldig enkelt å implementere!
Kompleksitet
tidskompleksiteten til denne algoritmen er i verste fall kvadratisk — O(n2). Som n rmer seg uendelig er gjennomsnittlig tilfelle n rmer seg verste fall delt med to. Men siden hvis listen din er sortert eller nesten så, kan Den Være O (n) i beste fall og dermed godt tilpasset det scenariet.
når det er raskt
som nevnt ovenfor kan det være raskt under visse omstendigheter. Tenk på arrayet, når du bruker en algoritme som merge sortering, vil vi fortsatt måtte dele alle elementene og deretter slå dem sammen igjen. Med innsetting sortering vi trenger bare å bekrefte at er i riktig ‘sortert så langt’ rekkefølge, så vi skifte dem alle opp en indeks for 1.
fordi innsettingssortering er en adaptiv sortering, gjør den det også til en online algoritme, noe som betyr at vi kan begynne å sortere før vi får alle elementene og deretter slå sammen lister når den delvise sorteringen er fullført.
Pseudokode
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Kode
Neste opp? Slå sammen sortering. En av de mest brukte sorteringsalgoritmer i nettlesere i dag.
