# Insättningssorteringsalgoritm
Översikt
Insättningssortering är en enkel sorteringsalgoritm som fungerar genom att infoga varje element i en array i dess korrekta position i arrayen. Den börjar med en tom sorterad array och itererar sedan genom inmatningsarrayen, och infogar varje element i sin korrekta position i den sorterade arrayen. Denna process upprepas tills hela inmatningsmatrisen är sorterad.
Algorithm Steg
Här är steg-för-steg-algoritmen för sortering av infogning:
1. Börja med en tom sorterad array.
2. Iterera genom inmatningsmatrisen.
3. För varje element i inmatningsmatrisen, infoga det på rätt plats i den sorterade matrisen.
4. För att infoga ett element, jämför det med varje element i den sorterade matrisen, börja med det första elementet.
5. Om elementet är mindre än det aktuella elementet i den sorterade arrayen, infoga det före det aktuella elementet.
6. Om elementet är större än det aktuella elementet i den sorterade arrayen, fortsätt att jämföra med nästa element i den sorterade arrayen.
7. Upprepa steg 4-6 tills elementet har satts in på rätt plats i den sorterade arrayen.
8. Upprepa steg 2-7 för varje element i inmatningsmatrisen.
Exempel
Låt oss överväga följande inmatningsmatris:
```
[5, 2, 8, 3, 1]
```
Följande steg visar hur sorteringsalgoritmen för infogning skulle sortera denna matris:
1. Börja med en tom sorterad array.
```
[]
```
2. Iterera genom inmatningsmatrisen.
```
[5]
```
3. För varje element i inmatningsmatrisen, infoga det på rätt plats i den sorterade matrisen.
```
[5]
```
4. För att infoga element 2, jämför det med varje element i den sorterade arrayen, börja med det första elementet.
```
[5, 2]
```
5. Eftersom 2 är mindre än 5, sätt in det före det aktuella elementet.
```
[2, 5]
```
6. Iterera genom inmatningsmatrisen.
```
[2, 5, 8]
```
7. För varje element i inmatningsmatrisen, infoga det på rätt plats i den sorterade matrisen.
```
[2, 5, 8]
```
8. För att infoga element 3, jämför det med varje element i den sorterade arrayen, börja med det första elementet.
```
[2, 3, 5, 8]
```
9. Eftersom 3 är mindre än 5, sätt in det före det aktuella elementet.
```
[2, 3, 5, 8]
```
10. Iterera genom inmatningsmatrisen.
```
[2, 3, 5, 8, 1]
```
11. För varje element i inmatningsmatrisen, infoga det på rätt plats i den sorterade matrisen.
```
[1, 2, 3, 5, 8]
```
12. För att infoga element 1, jämför det med varje element i den sorterade arrayen, börja med det första elementet.
```
[1, 2, 3, 5, 8]
```
13. Eftersom 1 är mindre än 2, infoga den före det aktuella elementet.
```
[1, 2, 3, 5, 8]
```
14. Den sorterade arrayen är nu klar.
```
[1, 2, 3, 5, 8]
```
Tidskomplexitet
Tidskomplexiteten för insättningssorteringen är O(n^2), där n är längden på inmatningsmatrisen. Detta innebär att körtiden för insättningssorteringen ökar kvadratiskt när storleken på inmatningsmatrisen ökar. Insättningssortering fungerar bäst när inmatningsmatrisen redan är nästan sorterad, i vilket fall dess tidskomplexitet är O(n).
Rymdens komplexitet
Insättningssortering kräver O(1) hjälputrymme, eftersom det bara behöver lagra en enda variabel (det aktuella elementet som infogas) utöver inmatningsmatrisen.
Fördelar och nackdelar
Insättningssortering har några fördelar och nackdelar:
Fördelar:
* Enkel att implementera
* Effektiv för små arrayer eller nästan sorterade arrayer
* Stabil sorteringsalgoritm (upprätthåller den relativa ordningen av lika element)
Nackdelar:
* Inte effektivt för stora arrayer
* Kvadratisk tidskomplexitet (O(n^2))
* Inte en på plats sorteringsalgoritm (kräver extra utrymme)
Slutsats
Insättningssortering är en enkel och effektiv sorteringsalgoritm som fungerar bra för små arrayer eller nästan sorterade arrayer. Dess enkelhet och stabilitet gör den till en användbar algoritm för utbildningsändamål och för specialiserade applikationer. Det är dock inte den mest effektiva sorteringsalgoritmen för stora arrayer, där effektivare algoritmer som quicksort eller merge sort bör användas.
