[👩‍💻알고리즘👩‍💻] 삽입 정렬

공부 자료 : 동빛나 유튜브 강의

1. 삽입 정렬이란?
   일련의 숫자를 정렬할 때, '필요한 경우에만' 각 숫자를 적절한 위치에 삽입하는 방식이다. 앞의 원소들이 이미 정렬이 되어 있다고 가정을 하는 특성 때문에 버블/선택 정렬보다 효율적이다.
   O(N^2)의 시간 복잡도를 가지며, 특정한 경우에는 굉장히 빠르게 작동하여 O(N^2)의 시간 복잡도를 가지는 세 가지 정렬 알고리즘 중에서는 가장 강력한 알고리즘이라고 할 수 있다.

1 10 5 8 7 6 4 3 2 9
1 10 5 8 7 6 4 3 2 9 : 10는 1 앞, 뒤에 위치할 수 있다. 10은 1보다 크기 때문에 뒤에 위치하게 된다.
1 10 _ 5 8 7 6 4 3 2 9 : 5는 1의 앞, 뒤, 10의 뒤에 위치할 수 있다. 5는 1보다 크고 10보다 작기 때문에 1과 10 사이에 위치한다.

1 5 10 8 7 6 4 3 2 9

이렇게 삽입하고자 하는 숫자 앞 부분은 이미 정렬이 되어 있기 때문에 추가적으로 그 안에서 또 정렬을 할 필요가 없다.
삽입 정렬은 필요한 만큼만 이동하기 때문에 버블/선택 정렬보다 효율적이다.

거의 정렬된 데이터에서는 삽입 정렬이 가장 빠를 수도 있따.
버블/선택은 정렬된 상태를 모르기 때문에 처음부터 끝까지 연산을 진행하여 느리다.