4.2 삽입 정렬 알고리즘 구현

삽입 정렬 알고리즘을 구현합시다. 시뮬레이션 함수 등은 앞과 같으므로 설명을 생략할게요.

void insertion_sort(Element *base, int n, Compare compare)

{

두 개의 반복문에서 사용할 변수를 선언하고 교환에 사용할 임시 변수도 선언할게요.

int i = 0, j=0;

Element temp;

외부 반복문은 정렬할 범위를 넓혀나가는 것입니다. 따라서 i를 1부터 n까지 점진적으로 증가할게요.

for(i=1; i<n; i++)

{

내부 반복문은 새롭게 범위에 포함한 원소의 위치를 찾아야 합니다. 따라서 j를 i로 초기화하고 점진적으로 줄여나갑니다.

for(j=i; j>0; j--)

{

만약 j번째 원소가 앞의 원소보다 크면 자리를 교환합니다.

if(compare(base[j-1],base[j])<0)

{

temp = base [j-1];

base[j-1] = base [j];

base[j] = temp;

}

그렇지 않을 때는 반복문을 탈출합니다.

else{ break; }

}