삽입 정렬(Insertion Sort) 알고리즘

삽입 정렬 알고리즘에 대해 정리하겠습니다.

 

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

삽입 정렬은 정렬되지 않은 순차적인(sequence) 데이터를 하나씩 리스트에 정렬하여 삽입하는 알고리즘입니다.

정렬된 부분의 맨 끝부터 새로운 데이터를 어디에 넣을지 비교하면서 알맞은 자리를 찾습니다.

 

처음에는 이해가 어려워 카드 놀이를 예시로 설명하겠습니다.

 

2. 삽입 정렬 Logic

1) 첫 번째 요소(1)은 이미 정렬된 것으로 간주하고, 2번째 부터 정렬을 시작합니다.

2) 두 번째 요소부터 마지막 요소까지 반복하면서, 현재 요소 'Key'를 앞의 정렬된 부분과 비교하여 올바른 위치에 삽입합니다.

3) 이 과정을 모든 요소가 정렬될 때까지 반복합니다.

 

3. 삽입 정렬 동작원리 ex)카드놀이

여러분은 친구들과 카드게임을 합니다. 인당 6장의 카드를 받는다고 할때, 당신은 5,2,4,6,1,3 이라는 숫자가 적힌 카드를 차례로 받았다고 가정해볼게요.

1) 초기상태: [5]. 첫 번째 요소는 비교할 대상이 없으므로 이미 정렬된 상태입니다.

2) 새로운 카드 2를 추가: 2는 5보다 작으므로, 5의 왼쪽에 삽입 -> [2,5]

3) 새로운 카드 4를 추가: 4는 5보다 작지만 2보다 크므로 2와 5사이에 삽입 -> [2,4,5]

4) 새로운 카드 6을 추가: 6은 모든 카드보다 크므로 가장 오른쪽에 정렬 -> [2,4,5,6]

5) 새로운 카드 1을 추가: 1은 모든 카드보다 작으므로 맨 왼쪽에 삽입 -> [1,2,4,5,6]

6) 새로운 카드 3을 추가: 3은 2보다 크고 4보다 작으므로 2와 4사이에 삽입 -> [1,2,3,4,5,6]

이 과정을 거치면 모든 카드가 오름차순으로 정렬됩니다.

이어서 코드로 알아보겠습니다.

 

4. 삽입 정렬 코드

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

 

1. 배열[A]의 두 번째 요소(j=2)부터 정렬을 시작합니다.

for j = 2 to length[A]

 

2. 2번째 배열의 값을 비교하기 위해 key에 저장해둡니다.

 

key = A[j]

 

3. i는 key와 비교할 대상의 인덱스이므로, 1을 빼서 앞의 인덱스를 선택합니다.

 

i = j - 1

 

4. 비교할 대상이자 key 앞에 있는 인덱스의 번호는 0보다는 커야합니다. 그리고 앞에 있는 값이 key값보다 크게 되면 정렬을 위한 while문이 실행됩니다.

while i > 0 and A[i] > key

 

5. 만약 앞에 같이 크다면, 값의 인덱스를 1을 더한 인덱스의 위치로 이동시킵니다.

A[i + 1] = A[i]

 

6. 5) 작업후 다시 비교하기 위해, i의 인덱스를 1을 빼서 하나 더 앞에 있는 값과 비교합니다.

i = i - 1

 

7. while문을 돌지 않는다면 i의 값보다 큰 것이므로, i+1 위치에 정렬합니다.

A[i + 1] = key

 

5. 시간 복잡도

- 최선의 경우: 모든 비교가 한 번에 끝나므로 시간 복잡도는 O(n)입니다.

- 최악의 경우: 배역이 역순인 경우 모든 요소를 비교해야하므로 O(n^2)입니다.