# Insertion Sort Algoritme
Oversigt
Indsættelsessortering er en simpel sorteringsalgoritme, der fungerer ved at indsætte hvert element i et array i dens korrekte position i arrayet. Det starter med et tomt sorteret array og itererer derefter gennem input-arrayet og indsætter hvert element i dens korrekte position i det sorterede array. Denne proces gentages, indtil hele input-arrayet er sorteret.
Algoritmetrin
Her er trin-for-trin-algoritmen for indsættelsessortering:
1. Start med et tomt sorteret array.
2. Gentag gennem input-arrayet.
3. For hvert element i input-arrayet skal du indsætte det i dens korrekte position i det sorterede array.
4. For at indsætte et element skal du sammenligne det med hvert element i det sorterede array, startende med det første element.
5. Hvis elementet er mindre end det aktuelle element i det sorterede array, skal du indsætte det før det aktuelle element.
6. Hvis elementet er større end det aktuelle element i det sorterede array, skal du fortsætte med at sammenligne med det næste element i det sorterede array.
7. Gentag trin 4-6, indtil elementet er indsat i sin korrekte position i det sorterede array.
8. Gentag trin 2-7 for hvert element i input-arrayet.
Eksempel
Lad os overveje følgende input-array:
```
[5, 2, 8, 3, 1]
```
De følgende trin viser, hvordan indsættelsessorteringsalgoritmen ville sortere dette array:
1. Start med et tomt sorteret array.
```
[]
```
2. Gentag gennem input-arrayet.
```
[5]
```
3. For hvert element i input-arrayet skal du indsætte det i dens korrekte position i det sorterede array.
```
[5]
```
4. For at indsætte element 2 skal du sammenligne det med hvert element i det sorterede array, startende med det første element.
```
[5, 2]
```
5. Da 2 er mindre end 5, skal du indsætte det før det aktuelle element.
```
[2, 5]
```
6. Gentag gennem input-arrayet.
```
[2, 5, 8]
```
7. For hvert element i input-arrayet skal du indsætte det i dens korrekte position i det sorterede array.
```
[2, 5, 8]
```
8. For at indsætte element 3 skal du sammenligne det med hvert element i det sorterede array, startende med det første element.
```
[2, 3, 5, 8]
```
9. Da 3 er mindre end 5, skal du indsætte det før det aktuelle element.
```
[2, 3, 5, 8]
```
10. Gentag gennem input-arrayet.
```
[2, 3, 5, 8, 1]
```
11. For hvert element i input-arrayet skal du indsætte det i dens korrekte position i det sorterede array.
```
[1, 2, 3, 5, 8]
```
12. For at indsætte element 1 skal du sammenligne det med hvert element i det sorterede array, startende med det første element.
```
[1, 2, 3, 5, 8]
```
13. Da 1 er mindre end 2, indsæt det før det aktuelle element.
```
[1, 2, 3, 5, 8]
```
14. Det sorterede array er nu færdigt.
```
[1, 2, 3, 5, 8]
```
Tidskompleksitet
Tidskompleksiteten af indsættelsessortering er O(n^2), hvor n er længden af inputarrayet. Dette betyder, at køretiden for indsættelsessortering øges kvadratisk, efterhånden som størrelsen af input-arrayet øges. Indsættelsessortering fungerer bedst, når input-arrayet allerede er næsten sorteret, i hvilket tilfælde dets tidskompleksitet er O(n).
Rumkompleksitet
Indsættelsessortering kræver O(1) hjælperum, da den kun skal gemme en enkelt variabel (det aktuelle element, der indsættes) ud over input-arrayet.
Fordele og ulemper
Indsættelsessortering har et par fordele og ulemper:
Fordele:
* Enkel at implementere
* Effektiv til små arrays eller næsten sorterede arrays
* Stabil sorteringsalgoritme (vedligeholder den relative rækkefølge af lige elementer)
Ulempe:
* Ikke effektiv til store arrays
* Kvadratisk tidskompleksitet (O(n^2))
* Ikke en in-place sorteringsalgoritme (kræver ekstra plads)
Konklusion
Indsættelsessortering er en enkel og effektiv sorteringsalgoritme, der fungerer godt for små arrays eller næsten sorterede arrays. Dens enkelhed og stabilitet gør den til en nyttig algoritme til uddannelsesformål og til specialiserede applikationer. Det er dog ikke den mest effektive sorteringsalgoritme til store arrays, hvor mere effektive algoritmer som quicksort eller merge sort bør bruges.
