# Insertion Sort Algoritme
Oversikt
Innsettingssortering er en enkel sorteringsalgoritme som fungerer ved å sette inn hvert element i en matrise i riktig posisjon i matrisen. Den starter med en tom sortert matrise og itererer deretter gjennom inngangsmatrisen, og setter inn hvert element i sin riktige posisjon i den sorterte matrisen. Denne prosessen gjentas til hele inndatamatrisen er sortert.
Algoritmetrinn
Her er trinn-for-trinn-algoritmen for innsettingssortering:
1. Start med en tom sortert matrise.
2. Iterer gjennom inndatamatrisen.
3. For hvert element i inndatamatrisen setter du det inn i riktig posisjon i den sorterte matrisen.
4. For å sette inn et element, sammenligne det med hvert element i den sorterte matrisen, og start med det første elementet.
5. Hvis elementet er mindre enn det gjeldende elementet i den sorterte matrisen, setter du det inn før det gjeldende elementet.
6. Hvis elementet er større enn det gjeldende elementet i den sorterte matrisen, fortsett å sammenligne med neste element i den sorterte matrisen.
7. Gjenta trinn 4-6 til elementet er satt inn i riktig posisjon i den sorterte matrisen.
8. Gjenta trinn 2-7 for hvert element i inndatamatrisen.
Eksempel
La oss vurdere følgende input-array:
```
[5, 2, 8, 3, 1]
```
Følgende trinn viser hvordan innsettingssorteringsalgoritmen vil sortere denne matrisen:
1. Start med en tom sortert matrise.
```
[]
```
2. Iterer gjennom inndatamatrisen.
```
[5]
```
3. For hvert element i inndatamatrisen setter du det inn i riktig posisjon i den sorterte matrisen.
```
[5]
```
4. For å sette inn element 2, sammenligne det med hvert element i den sorterte matrisen, og start med det første elementet.
```
[5, 2]
```
5. Siden 2 er mindre enn 5, sett den inn før det gjeldende elementet.
```
[2, 5]
```
6. Iterer gjennom inndatamatrisen.
```
[2, 5, 8]
```
7. For hvert element i inndatamatrisen setter du det inn i riktig posisjon i den sorterte matrisen.
```
[2, 5, 8]
```
8. For å sette inn element 3, sammenlign det med hvert element i den sorterte matrisen, start med det første elementet.
```
[2, 3, 5, 8]
```
9. Siden 3 er mindre enn 5, sett den inn før det gjeldende elementet.
```
[2, 3, 5, 8]
```
10. Iterer gjennom inndatamatrisen.
```
[2, 3, 5, 8, 1]
```
11. For hvert element i inndatamatrisen setter du det inn i riktig posisjon i den sorterte matrisen.
```
[1, 2, 3, 5, 8]
```
12. For å sette inn element 1, sammenlign det med hvert element i den sorterte matrisen, start med det første elementet.
```
[1, 2, 3, 5, 8]
```
13. Siden 1 er mindre enn 2, sett den inn før det gjeldende elementet.
```
[1, 2, 3, 5, 8]
```
14. Den sorterte matrisen er nå fullført.
```
[1, 2, 3, 5, 8]
```
Tidskompleksitet
Tidskompleksiteten til innsettingssortering er O(n^2), der n er lengden på inngangsmatrisen. Dette betyr at kjøretiden for innsettingssortering øker kvadratisk ettersom størrelsen på inngangsmatrisen øker. Innsettingssortering fungerer best når inngangsmatrisen allerede er nesten sortert, i så fall er tidskompleksiteten O(n).
Romkompleksitet
Innsettingssortering krever O(1) hjelperom, siden den bare trenger å lagre en enkelt variabel (det gjeldende elementet som settes inn) i tillegg til inngangsmatrisen.
Fordeler og ulemper
Innsettingssortering har noen fordeler og ulemper:
Fordeler:
* Enkel å implementere
* Effektiv for små arrays eller nesten sorterte arrays
* Stabil sorteringsalgoritme (opprettholder den relative rekkefølgen av like elementer)
Ulemper:
* Ikke effektiv for store matriser
* Kvadratisk tidskompleksitet (O(n^2))
* Ikke en på stedet sorteringsalgoritme (krever ekstra plass)
Konklusjon
Innsettingssortering er en enkel og effektiv sorteringsalgoritme som fungerer godt for små arrays eller nesten sorterte arrays. Dens enkelhet og stabilitet gjør den til en nyttig algoritme for pedagogiske formål og for spesialiserte applikasjoner. Det er imidlertid ikke den mest effektive sorteringsalgoritmen for store arrays, der mer effektive algoritmer som quicksort eller merge sort bør brukes.
