삽입 정렬(Insertion Sort)이란?

삽입 정렬은 각 반복에서 하나의 요소를 적절한 위치에 '삽입'함으로써 배열이나 리스트를 정렬합니다.

이 방법은 비교적 직관적이며 구현이 간단하지만, 데이터의 양이 많아질수록 효율성이 떨어집니다.

1. 첫 번째 요소부터 시작: 배열의 첫 번째 요소는 이미 정렬된 것으로 간주하고, 두 번째 요소부터 정렬 과정을 시작합니다.

2. 현재 요소 선택: 현재 정렬할 요소를 선택합니다.

3. 적절한 위치 찾기: 선택한 요소를 이미 정렬된 배열 부분의 적절한 위치에 삽입합니다. 이를 위해 선택한 요소보다 큰 요소들을 오른쪽으로 이동시킵니다.

4. 반복 수행: 배열의 모든 요소에 대해 이 과정을 반복합니다.