삽입 정렬(Insertion Sort) - 정의 / 예시 코드

 

삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다.

 

아래는 삽입 정렬의 동작 과정을 단계별로 설명한 것입니다.

 

1. 주어진 배열을 순회합니다.

2. 배열의 첫 번째 원소는 이미 정렬되었다고 간주합니다.

3. 다음 원소부터 시작하여 정렬되지 않은 부분의 원소를 하나씩 선택합니다.

4. 선택한 원소를 정렬된 부분의 올바른 위치에 삽입합니다.
    - 선택한 원소를 정렬된 부분의 마지막 원소부터 비교하며, 적절한 위치를 찾아갑니다.
    - 선택한 원소보다 큰 값이 나올 때까지 이전 원소를 한 칸씩 오른쪽으로 이동시킵니다.
    - 적절한 위치를 찾으면 선택한 원소를 해당 위치에 삽입합니다.

5. 모든 원소를 정렬된 부분에 삽입할 때까지 위의 과정을 반복합니다.

 

반응형

 

아래는 C++로 구현된 예시 코드입니다.

 

 

위의 예시 코드를 실행하면, 배열 {64, 34, 25, 12, 22, 11, 90}가 오름차순으로 정렬되어 {11, 12, 22, 25, 34, 64, 90}가 출력됩니다.

삽입 정렬은 배열의 크기가 작을 때 성능이 좋으며, 최선의 경우 시간 복잡도는 O(n)입니다. 하지만 배열의 크기가 커질수록 비교와 교환 연산의 수가 증가하므로, 평균 및 최악의 경우 시간 복잡도는 O(n^2)입니다.