[정령알고리즘] - 2. 삽입정렬(Insertion Sort)

삽입정렬 알고리즘은 선택정렬과 함께 가장 많이 사용되고 간단한 방법의 정렬법이다. 선택정렬이 많은 비교와 적은 교환을 수행한다면 삽입정렬은 그와 반대되게 많은 교환과 적은 비교로 수행된다.

삽입정렬은 주어진 데이터의 2번째 부터 선택하여 그 앞쪽의 데이터와 대,소를 비교하여 작다면 앞쪽의 데이터를 뒤로 보내고 삽입할 공간을 마련해두고 삽입하게 된다.

구현은 아래와 같다.
void Insertion_Sort(int ary[], int nSize) { int nTmp = 0; int j = 0; //2번째 데이터 부터 선택해서 루프를 수행.. for(int i = 1; i < nSize; i++) { nTmp = ary[i]; j = i; //선택된 키값보다 앞에 있는 값이 크고 데이터의 시작 지점이 아닐경우 //삽입할 공간을 만듬... while(ary[j-1] > nTmp && j > 0) { ary[j] = ary[j-1]; j--; } //만들어진 공간에 삽입.. ary[j] = nTmp; } }

<성능 테스트>

데이터 갯수	수행시간
10000	125
20000	474