삽입 정렬(insert sort)

<삽입 정렬(insert sort)>

정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 

 

정렬할 자료를 두 개의 부분집합 S와 U로 가정
부분집합 S : 정렬된 앞부분의 원소들
부분집합 U : 아직 정렬되지 않은 나머지 원소들 

 

정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다. 

 

[삽입 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자. 

 

초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고, 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.

S={69} , U={10, 30, 2, 16, 8, 31, 22}

① U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69) 이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할 S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.
S={10, 69} , U={30, 2, 16, 8, 31, 22}

② U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69)이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10) 이므로 원소 10과 69 사이에 삽입한다.
•S={10, 30, 69} , U={2, 16, 8, 31, 22}

③ U의 첫 번째 원소 2를 S의 마지막 원소 69와 비교하여 (2 < 69) 이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데, (2 < 10) 이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.
•S={2, 10, 30, 69} , U={16, 8, 31, 22}

④ 이런 작업을 반복한다.

 

⑤ U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69)이므로 그 앞자리 원소 31과 비교한다.
(22 < 31) 이므로 그 앞자리 원소 30과 비교하고,
(22 < 30) 이므로 다시 그 앞자리 원소 16과 비교하여,
(22 > 16) 이므로 원소 16과 30 사이에 삽입한다.
•S={2, 8, 10, 16, 22, 30, 31, 69} , U={}

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)