반응형
정렬 알고리즘인 삽입 정렬입니다.
배열의 앞쪽부터 시작해서 순회하면서 정렬을 합니다.
그리고 앞 부분의 정렬된 부분에서 선택된 값의 위치를 찾아서 이동시키는 알고리즘입니다.
기본적으로 버블 소트나 선택 정렬보다 성능이 좋고 구현이 간편한 장점이 있는 정렬입니다.
또한 추가적인 메모리가 크게 필요 없는 In-Place 알고리즘입니다.
반복문을 돌리기 위한 변수와 swap을 위한 변수 정도가 추가로 필요합니다.
그리고 같은 값이 있을 때 그 순서가 변경되지 않는 안정 정렬입니다.
Wiki에서 확인할 수 있는 삽입 정렬의 정렬 방식입니다.
http://en.wikipedia.org/wiki/Insertion_sort
이 영상이 삽입 정렬의 모든 것을 보여주고 있습니다.
두 번째 값부터 시작해서 각각의 값들이 앞부분의 정렬된 부분에서 자신의 자리를 찾습니다.
삽입 정렬의 소스 코드는 다음과 같습니다.
#include <iostream> template <typename T> void InsertionSort(T* arrVal, int nNum) { int i, j; T remember; for (i = 1 ; i < nNum ; ++i) { remember = arrVal[i]; for (j = i ; j > 0 ; --j) { if (arrVal[j - 1] > remember) { arrVal[j] = arrVal[j - 1]; } else { break; } } arrVal[j] = remember; } } void main() { using std::cout; using std::endl; int nVec[] = {5, 10, 6, 7, 9, 3, 4, 1, 2, 8}; cout << "Before : "; for (int i = 0; i < _countof(nVec) ; ++i) cout << nVec[i] << " "; cout << endl; InsertionSort(nVec, _countof(nVec)); cout << "After : "; for (int i = 0; i < _countof(nVec); ++i) cout << nVec[i] << " "; cout << endl; }
코드도 상당히 단순합니다.
두 번째 원소부터 선택해서 계속 뒤로 이동하면서 앞 부분의 정렬된 부분과 비교합니다.
더 큰 값이 있으면 계속 뒤로 밀어내다가 같거나 작은 값이 있으면 멈추고 값을 위치시킵니다.
참고로 _countof()는 MS Visual C++에서만 사용이 가능한 것으로 알고 있습니다.
다른 컴파일러를 사용할 때는 sizeof() / sizeof()로 변경하거나 하면 됩니다.
비교적 간단한 정렬 알고리즘으로 역시 성능이 뛰어나진 않기 때문에 잘 사용되지 않습니다.
반응형
'Programming > Algorithm' 카테고리의 다른 글
[정렬 알고리즘] 퀵 소트(Quick Sort) (0) | 2018.05.18 |
---|---|
2개의 스택(Stack)으로 큐(Queue) 구현하기 (0) | 2017.03.15 |
[정렬 알고리즘] 선택 정렬(Selection Sort) (0) | 2014.12.09 |
[정렬 알고리즘] 버블 소트(거품정렬) (0) | 2014.12.07 |
간단한 GCD 알고리즘(Euclid 호제법) (0) | 2014.11.21 |