삽입 정렬(Insertion Sort)은 비교 기반의 정렬 알고리즘으로, 배열의 각 요소를 순차적으로 선택하여 적절한 위치에 삽입하면서 배열을 정렬하는 방식이다. 이 알고리즘은 현재 배열의 일부분을 이미 정렬된 상태로 유지하면서, 새로운 요소를 삽입하는 방식으로 작동한다. 거의 정렬된 데이터에서 매우 효율적으로 동작하며, 구현이 간단하고 직관적인 특징이 있다.동작 방식 초기 상태: 첫 번째 요소는 이미 정렬된 것으로 가정한다.두 번째 요소부터 시작: 배열의 두 번째 요소를 선택한다.왼쪽에 있는 정렬된 부분과 비교: 선택한 요소를 왼쪽의 정렬된 부분에 삽입할 적절한 위치를 찾기 위해 비교한다.삽입: 비교하여 자신보다 큰 값들은 한 칸씩 오른쪽으로 이동시키고, 자신의 자리를 찾으면 그 위치에 삽입한다.반복:..
