삽입 정렬에 대해 설명해 주세요.

• 삽입 정렬(Insertion Sort)는 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘이다.

• 평균 시간복잡도는 O(N^2)이며, 최선의 경우 O(N)까지 높아질 수 있다.

img_2.png

참고 영상