den här artikeln är en del av en serie som täcker sorteringsalgoritmer i JavaScript. Resten av serien hittar du här. Om du är ny på sorteringsalgoritmer, eller algoritmer i allmänhet, läs detta först för att få en solid grund för att gå vidare. Idag kommer jag att täcka ins och outs av insertion sort. Infogningssortering är mer komplex men lite mer användbar än bubbelsortering. Det värsta scenariot för det liknar bubble sort men det bästa fallet gör det lämpligt för tider när du är ganska säker på att en lista nästan sorteras eller sannolikt redan sorteras. Låt oss få den stora bilden.
Insertion sort fungerar genom att titta på varje element i en lista (börjar med det andra elementet) och jämföra det med objektet innan. Om objektet innan är större byts de ut. Detta fortsätter tills objektet är mindre vid vilken tidpunkt vi gör detsamma för nästa element i listan.
insättningssortering är inte så illa.. så länge du använder det under rätt omständigheter.
- det är snabbare än de flesta o(n log n) sorteringsalgoritmer för små listor.
- det är extremt minneseffektivt och kräver endast o (1) extra utrymme för det enskilda objektet som flyttas.
- det är stabilt — lika element visas i samma ordning i den sorterade listan.
- det är adaptivt-det är snabbt när du sorterar mestadels sorterade listor eller när du lägger till objekt i en redan sorterad lista.
- det är väldigt enkelt att implementera!
komplexitet
tidskomplexiteten för denna algoritm är i värsta fall kvadratisk — O(n2). När n närmar sig oändligheten närmar sig det genomsnittliga fallet det värsta fallet dividerat med två. Men eftersom om din lista är sorterad eller nästan så kan den vara O(n) i bästa fall och därmed väl anpassad till det scenariot.
när det är snabbt
som nämnts ovan kan det vara snabbt under vissa omständigheter. Tänk på arrayen, när du använder en algoritm som merge sort skulle vi fortfarande behöva dela upp alla objekt och sedan slå ihop dem igen. Med insättning Sortera vi behöver bara kontrollera att är i rätt ’sorterade hittills’ ordning, då vi flytta dem alla upp ett index för 1.
eftersom insättningssortering är en adaptiv sortering gör den det också till en ’onlinealgoritm’, vilket innebär att vi kan börja sortera innan vi får alla objekt och sedan slå samman listorna när den partiella sorteringen har slutförts.
pseudokod
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
kod
Nästa upp? Slå samman Sortera. En av de mest använda sorteringsalgoritmerna i webbläsare idag.
