Dit artikel is onderdeel van een serie bekleding soort algoritmen in JavaScript. De rest van de serie vindt u hier. Als je nieuw bent in het sorteren van algoritmen, of algoritmen in het algemeen, lees dit eerst om een solide basis te krijgen om vooruit te gaan. Vandaag zal ik de ins en outs van insertion sort behandelen. Insertion sort is complexer maar iets nuttiger dan bubble sort. Het slechtste scenario voor het is vergelijkbaar met bubble sort ‘ s, maar zijn beste geval maakt het geschikt voor tijden wanneer je vrij zeker bent dat een lijst bijna gesorteerd of waarschijnlijk al gesorteerd. Laten we het grote plaatje zien.
Insertion sort werkt door naar elk element in een lijst te kijken (te beginnen met het tweede element) en het te vergelijken met het voorgaande item. Als het item eerder groter is, worden ze verwisseld. Dit gaat door totdat het item kleiner is, waarna we hetzelfde doen voor het volgende element in de lijst.
invoegen is niet zo slecht.. als je het maar in de juiste omstandigheden gebruikt.
- het is sneller dan de meeste o(n log n) sorteeralgoritmen voor kleine lijsten.
- het is extreem geheugenefficiënt en vereist alleen O (1) extra ruimte voor het ene item dat wordt verplaatst.
- de stabiele-gelijke elementen verschijnen in dezelfde volgorde in de gesorteerde lijst.
- het is adaptief-het is snel bij het sorteren van meestal gesorteerde lijsten of bij het toevoegen van items aan een reeds gesorteerde lijst.
- het is zeer eenvoudig te implementeren!
complexiteit
de tijdscomplexiteit van dit algoritme is in het slechtste geval kwadratisch — O(n2). Als n oneindig nadert, benadert het gemiddelde geval het slechtste geval gedeeld door twee. Maar omdat als uw lijst is gesorteerd of bijna Zo, kan het O (n) in het beste geval scenario en dus goed aangepast aan dat scenario.
wanneer het snel is
zoals hierboven vermeld, kan het onder bepaalde omstandigheden snel zijn. Overweeg de array, wanneer we een algoritme gebruiken zoals merge sort zouden we nog steeds alle items moeten splitsen en ze vervolgens weer moeten samenvoegen. Met insertion sort hoeven we alleen maar te controleren of ze in de juiste ‘gesorteerd tot nu toe’ volgorde staan, dan verschuiven we ze allemaal één index naar boven voor 1.
omdat Invoeg sortering een adaptieve sortering is, maakt het ook een ‘online algoritme’, wat betekent dat we kunnen beginnen met sorteren voordat we alle items krijgen en vervolgens de lijsten samenvoegen zodra de gedeeltelijke sortering is voltooid.
Pseudocode
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
Code
de volgende? Soort samenvoegen. Een van de meest gebruikte sorteeralgoritmen in browsers vandaag.
