[카테고리:] <span>자료구조와 알고리즘</span>

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

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;    }
        }
    }
}

다음은 알고리즘 진행 과정을 확인할 수 있는 소스 코드입니다.