1. 삽입 정렬(Insertion Sort)?
삽입 정렬은 원소들을 정렬된 영역에서 원소가 들어갈 위치를 찾아서 삽입하는 과정을 반복하여 정렬을 행하는 알고리즘입니다.
2. 예시
5
|
1
|
3
|
8
|
7
|
데이터를 가지고 직접 삽입 정렬을 해봅시다.
1. 삽입할 원소를 기억해둔다.
5
|
1
|
3
|
8
|
7
|
2. 정렬된 구간(삽입된 원소의 앞쪽 구간)에서 원소가 삽입될 위치를 찾으면서, 삽입될 공간을 확보하기 위해 원소들을 뒤로 옮겨준다.
5
|
5
|
3
|
8
|
7
|
3. 삽입될 위치를 찾았으면, 기억해둔 원소를 넣는다.
1
|
5
|
3
|
8
|
7
|
4. 1~3을 반복한다.
1
|
5
|
3
|
8
|
7
|
1
|
5
|
5
|
8
|
7
|
1
|
5
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
8
|
1
|
3
|
5
|
8
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
3. 특징
삽입정렬은 원소를 정렬된 영역에 추가로 삽입하는 동작을 반복하기 때문에, 이미 정렬된 배열은 매우 짧은 시간에 정렬작업이 완료된다. 또한, 정렬된 배열에 이미 원소가 추가되는 형태의 경우, 추가된 원소에 대해서만 정렬을 수행하게 되는 특징이 있다. 하지만, 반대로 정렬된 배열의 경우 모든 원소들에 대해 비교 연산을 수행하게 되어 최악수행시간이 된다. 최악의 경우 이미 정렬된 배열에 대해 비교연산을 전부 수행하므로 1+2+3+...+N이 되어 O(N^2)이 된다.
4. C를 이용한 구현
삽입될 원소가 이미 정렬된 원소들보다 작은 경우 배열의 밖을 참조하려고 하는 일이 발생할 수 있으므로, 예외처리가 필요하다. 이를 하지 않고 맨앞에 매우 작은 값으로 '보초'를 넣는 기법도 생각해 볼 수 있으나, 상황에 따라 이것이 불가능 할 수 있으므로, 주의가 필요하다.
댓글 없음:
댓글 쓰기