4.2 삽입 정렬 알고리즘 구현

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

        }

    }

}