정렬: 삽입 정렬

출처: 위키백과

삽입 정렬이란?

삽입 정렬(Insertion Sort)은 배열의 요소를 하나씩 확인하며, 각 요소를 이미 정렬된 배열 부분의 적절한 위치에 '삽입'하는 방식으로 정렬을 수행하는 알고리즘입니다. 이 과정은 카드 게임에서 손에 든 카드를 정렬하는 방식과 유사합니다.

 

삽입 정렬의 작동 원리

삽입 정렬에서는 배열의 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분의 적절한 위치에 삽입합니다. 이는 요소를 하나씩 올바른 위치로 이동시키는 것으로, 각 단계에서 배열의 정렬된 부분은 확장되며, 정렬되지 않은 부분은 줄어듭니다.

 

삽입 정렬의 단계별 과정

1. 두 번째 요소부터 시작하여 현재 요소를 복사합니다.
2. 현재 요소보다 앞에 있는 정렬된 배열 부분과 비교하여 적절한 위치를 찾습니다.
3. 정렬된 부분의 요소들을 뒤로 이동시킨 후, 현재 요소를 빈 자리에 삽입합니다.
4. 다음 요소로 이동하여 위의 과정을 배열의 끝까지 반복합니다.

삽입 정렬의 복잡도

시간 복잡도: 삽입 정렬은 최악의 경우 각 요소가 앞의 모든 요소와 비교되므로 O(n^2)의 시간 복잡도를 가집니다. 하지만 부분적으로 정렬된 배열에서는 훨씬 더 효율적일 수 있습니다.
공간 복잡도: O(1)로, 추가적인 메모리 공간은 하나만 필요합니다.

 

Pseudocode

for i from 1 to N-1
  key = array[i]
  j = i - 1
  while j >= 0 and array[j] > key
    array[j + 1] = array[j]
    j = j - 1
  array[j + 1] = key

 

실제 예시로 이해하기

예를 들어, [7, 5, 3, 8, 4] 이라는 배열을 오름차순으로 정렬한다고 해봅시다. 삽입 정렬 과정은 다음과 같습니다:

1. 두 번째 요소(5)를 현재 요소로 선택하고, 첫 번째 요소(7)와 비교하여 5를 앞에 삽입합니다: [5, 7, 3, 8, 4]
2. 세 번째 요소(3)를 현재 요소로 선택하고, 앞의 요소들과 비교하여 3을 앞에 삽입합니다: [3, 5, 7, 8, 4]
3. 네 번째 요소(8)는 이미 올바른 위치에 있으므로 삽입 위치를 변경할 필요가 없습니다.
4. 다섯 번째 요소(4)를 현재 요소로 선택하고, 앞의 요소들과 비교하여 4를 적절한 위치에 삽입합니다: [3, 4, 5, 7, 8]

결과적으로 오름차순으로 정렬된 배열 [3, 4, 5, 7, 8]을 얻을 수 있습니다.

 

삽입 정렬은 그 구현이 간단하고, 작은 데이터 세트나 거의 정렬된 배열에 매우 효과적입니다. 간단하면서도 효과적인 이 알고리즘은 알고리즘을 이해하는데 있어 기본이 되며, 특히 실시간으로 데이터가 추가되는 경우에 유용하게 사용될 수 있습니다.