알고리즘의 기본 - 삽입 정렬(Insertion Sort) 이해하기(코드)

1. 삽입 정렬(Insertion Sort)이란?

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 데이터를 하나씩 확인하면서 올바른 위치에 삽입하여 정렬하는 방식입니다. 간단한 원리로 동작하며 거의 정렬된 데이터를 처리할 때 매우 효율적입니다. 하지만 일반적인 경우 시간 복잡도가 O(n²)로 비효율적이므로 대량의 데이터 정렬에는 적합하지 않습니다.

 

2. 삽입 정렬의 원리

삽입 정렬은 다음과 같은 단계를 거쳐 정렬을 수행합니다.

1. 두 번째 요소부터 시작하여 현재 요소를 정렬된 부분과 비교한다.
2. 현재 요소보다 큰 값들을 오른쪽으로 이동시킨다.
3. 현재 요소를 올바른 위치에 삽입한다.
4. 리스트의 모든 요소에 대해 위 과정을 반복한다.

 

<예시> [ 8, 4, 6, 2, 9 ]를 오름차순으로 정렬하는 과정을 살펴보겠습니다.

1. 첫 번째 요소(8)는 정렬된 상태로 간주
2. 두 번째 요소(4)를 정렬된 부분과 비교 후 삽입 → [ 4, 8, 6, 2, 9 ]
3. 세 번째 요소(6)를 정렬된 부분과 비교 후 삽입 → [ 4, 6, 8, 2, 9 ]
4. 네 번째 요소(2)를 정렬된 부분과 비교 후 삽입 → [ 2, 4, 6, 8, 9 ]
5. 다섯 번째 요소(9)는 이미 정렬된 상태 → [ 2, 4, 6, 8, 9 ] (완료)

 

3. 삽입 정렬의 시간 복잡도

T(n): 각 줄의 비용과 실행 횟수의 곱을 모두 더한 값

 

삽입 정렬의 시간 복잡도는 다음과 같습니다.

• 최선의 경우 (Best Case) : O(n) (이미 정렬된 경우)
• 평균의 경우 (Average Case) : O(n²)
• 최악의 경우 (Worst Case) : O(n²) (역순 정렬된 경우)

최선의 경우, 즉 데이터가 이미 정렬된 경우에는 한 번씩만 비교하므로 O(n)의 성능을 가집니다.

하지만 데이터가 무작위로 배치되어 있거나 역순으로 정렬되어 있는 경우, 모든 요소를 비교하고 이동해야 하므로 O(n²)의 성능을 갖습니다.

 

4. 삽입 정렬의 장점과 단점

⭕ 장점

• 구현이 쉽고 직관적이다.
• 거의 정렬된 데이터에서 매우 효율적이다. (시간 복잡도 : O(n) )
• 추가적인 메모리 공간을 거의 사용하지 않는다 (in-place sorting).

❌ 단점

• 일반적인 경우 O(n²)의 시간 복잡도를 가지므로 큰 데이터셋에서는 비효율적이다.
• 역순으로 정렬된 데이터에서는 성능이 매우 저하된다.

 

5. 삽입 정렬 구현

pseudo code

INSERTION-SORT(A)
1 for j = 2 to A.length
2     key = A[j]
3     // Insert A[j] into the sorted sequence A[1..j - 1].
4     i = j - 1 
5     while i > 0 and A[i] > key
6         A[i + 1] = A[i]
7         i = i - 1
8     A[i + 1] = key

 

1번째 줄 : 반복문 시작 (for j = 2 to A.length)
   리스트의 두 번째 요소부터 마지막 요소까지 반복하면서 정렬을 수행합니다.

2번째 줄 :  현재 정렬할 값 선택 (key = A[j]):
   현재 삽입할 값을 key 변수에 저장합니다.

5번째 줄 :  정렬된 부분 배열과 비교 (while i > 0 and A[i] > key):
   i는 현재 요소 A[j]의 이전 요소를 가리킵니다.
   A[i]가 key보다 크다면, A[i]를 오른쪽으로 이동시킵니다.
   이 과정은 key가 적절한 위치에 삽입될 때까지 반복됩니다.

6번째 줄 :  원소 이동 (A[i + 1] = A[i]):
   A[i]를 한 칸 오른쪽으로 이동하여 key를 삽입할 공간을 만듭니다.

7번째 줄 :  현재 위치 업데이트 (i = i - 1):
   i를 감소시켜 계속해서 왼쪽의 요소와 비교합니다.

8번째 줄 :  삽입 완료 (A[i + 1] = key):
  최종적으로 key 값을 적절한 위치에 삽입합니다.

 

Python code

# 삽입 정렬 알고리즘 구현
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 예제 실행
arr = [8, 4, 6, 2, 9]
sorted_arr = insertion_sort(arr)
print("정렬된 배열:", sorted_arr)