2.4 삽입 정렬(Insertion Sort) [디딤돌 자료구조와 알고리즘 with C++]

2.4 삽입 정렬(Insertion Sort)

이번에는 반복적인 방법으로 해결하는 삽입 정렬(Insertion Sort) 알고리즘을 살펴볼게요.

 

삽입 정렬도 순차 정렬처럼 맨 앞에서부터 정렬 범위를 확장해 나가는 알고리즘이예요. 차이점은 확장할 범위의 끝에 있는 원소를 앞의 원소와 비교하며 자신보다 크면 위치를 바꾸고 그렇지 않으면 반복을 멈춘다는 것이죠. 순차 정렬에서 확장할 위치에 배치할 원소를 뒤쪽 원소와 비교하며 교환했지만 삽입 정렬에서는 확장할 위치에 있는 원소를 앞의 원소와 비교하며 교환하며 자신의 위치를 찾는다는 것이 다릅니다.

삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=1->n)

        반복(j:=i->1)

            조건(compare(base[j-1], base[j]) > 0)

                교환(base[j-1],base[j])

            조건이 거짓일 때

                내부 반복문 탈출

예:

2 9 4 1 5 6 8 3 7       (정렬 전, n:9)

2 9 4 1 5 6 8 3 7       (i:1, j:1), 1회전 완료

2 9 4 1 5 6 8 3 7       (i:2, j:2)

2 4 9 1 5 6 8 3 7       (i:2, j:2), 교환

2 4 9 1 5 6 8 3 7       (i:2, j:1), 내부 반복문 탈출, 2회전 완료

2 4 9 1 5 6 8 3 7       (i:3, j:3)

2 4 1 9 5 6 8 3 7       (i:3, j:3), 교환

2 4 1 9 5 6 8 3 7       (i:3, j:2)

2 1 4 9 5 6 8 3 7       (i:3, j:2), 교환

2 1 4 9 5 6 8 3 7       (i:3, j:1)

1 2 4 9 5 6 8 3 7       (i:3, j:1), 교환, 3회전 완료

1 2 4 9 5 6 8 3 7       (i:4, j:4)

1 2 4 5 9 6 8 3 7       (i:4, j:4), 교환

1 2 4 5 9 6 8 3 7       (i:4, j:3), 내부 반복문 탈출, 4회전 완료

1 2 4 5 9 6 8 3 7       (i:5, j:5)

1 2 4 5 6 9 8 3 7       (i:5, j:5), 교환

1 2 4 5 6 9 8 3 7       (i:5, j:4), 내부 반복문 탈출, 5회전 완료

1 2 4 5 6 9 8 3 7       (i:6, j:6)

1 2 4 5 6 8 9 3 7       (i:6, j:6), 교환

1 2 4 5 6 8 9 3 7       (i:6, j:5), 내부 반복문 탈출, 6회전 완료

1 2 4 5 6 8 9 3 7       (i:7, j:7)

1 2 4 5 6 8 3 9 7       (i:7, j:7), 교환

1 2 4 5 6 8 3 9 7       (i:7, j:6)

1 2 4 5 6 3 8 9 7       (i:7, j:6), 교환

1 2 4 5 6 3 8 9 7       (i:7, j:5)

1 2 4 5 3 6 8 9 7       (i:7, j:5), 교환

... 생략 ...

 

2.4.1 삽입 정렬 알고리즘 분석

이번에는 삽입 정렬 알고리즘을 분석해 보기로 해요.

삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=1->n)

        반복(j:=i->0)

            조건(compare(base[j-1], base[j]) > 0)

                교환(base[j-1],base[j])

            조건이 거짓일 때

                내부 반복문 탈출

 

삽입 정렬 알고리즘을 보면 반복문 내부에 반복문이 있는 구조입니다. 먼저 내부의 반복문에서 하는 일이 무엇인지 알아봅시다.

 

삽입 정렬 알고리즘의 내부 반복문에서는 j값을 i부터 0까지 점점 감소하며 작업을 수행하죠. 따라서 루프 변성은 j값이 변하는 것이예요. 그리고 배열의 j-1번째 요소와 j번째 요소와 비교하여 j번째 요소가 작으면 위치를 교환하죠. 이처럼 수행하면 배열의 j번째 요소부터 i번째 요소 중에서 제일 작은 값이 있는 위치는 j이죠. 따라서 루프 불변성은 배열의 j번째 요소부터 i번째 요소 중에서 제일 작은 값은 j번째에 있다는 것이예요. 특히 내부 반복문을 수행하기 전에 선행 조건이 i 이전의 요소들은 정렬 상태라는 것이예요. 따라서 내부 반복문을 수행하면 i번째 요소까지 정렬 상태로 변합니다.

 

이번에는 내부 반복문을 감싸고 있는 외부 반복문을 살펴보아요. i는 1에서 n까지 순차적으로 증가하고 있어요. 내부 반복문을 수행하면 i번째 요소까지 정렬 상태로 변하죠. 따라서 외부 반복문을 수행하면 전체 요소를 정렬할 수 있다는 것을 증명할 수 있어요.

 

이번에는 삽입 정렬 알고리즘 성능을 분석합시다.

 

삽입 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i에서 0까지 점점 감소하므로 최악일 때 비교를 i번 수행하고 교환도 i번 수행함을 알 수 있어요. 따라서 S(i) = 2n 이죠.

 

외부 반복문은 i가 1에서 n까지 순차적으로 증가하면서 내부 반복문을 수행합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(1) + S(2)+ ... +S(n) 이죠.

 

따라서 T(n) = S(1) + S(2)+ ... +S(n) = 2(1 + 2 + ... + n)

따라서 T(n)= n(n+1) 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 삽입 정렬도 순차 정렬과 거품 정렬, 선택 정렬처럼 O(n^2)이네요.

 

하지만 앞에서부터 특정 위치까지 정렬 상태에서 삽입 정렬을 사용하면 다른 정렬 방식에 비해 뛰어난 성능을 발휘할 수 있습니다.

 

 

 

 

 

2.4.2 삽입 정렬 알고리즘 구현

이번에는 삽입 정렬 알고리즘을 구현해 보기로 해요.

삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=1->n)

        반복(j:=i->0)

            조건(compare(base[j-1], base[j]) > 0)

                교환(base[j-1],base[j])

            조건이 거짓일 때

                내부 반복문 탈출

 

참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.

template <typename data, typename compare>

//삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

void insertion_sort(data *base, size_t n, compare com)

{

    for(size_t i=1; i<n; i++)//반복(i:=1->n)

    {

        for(size_t j=i; j>0;j--)//반복(j:=i->1)

        {

            if(com(base[j-1],base[j])>0)//조건(compare(base[j-1], base[j]) > 0)

            {

                swap(base[j-1], base[j]);//교환(base[j],base[j-1])

            }

            else//조건이 거짓일 때

            {

                break;//내부 반복문 탈출

            }

        }

    }

}

 

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 insertion_sort로 변경하세요.

#define MAX_DATA 1000

 

int main()

{

    Member *base[MAX_DATA];

삽입 정렬이 잘 동작하는지 10개 원소를 번호 순으로 정렬하여 확인하고 이름 순으로 정렬하여 확인하세요.

    MakeRandomMembers(base,10);

    cout<<"정렬 전"<<endl;

    ViewMembers(base,10);

    insertion_sort(base,10,CompareByNum);

    cout<<"번호로 정렬 후"<<endl;

    ViewMembers(base,10);

    insertion_sort(base,10,CompareByName);

    cout<<"이름으로 정렬 후"<<endl;

    ViewMembers(base,10);

    RemoveMembers(base,10);

 

그리고 MAX_DATA 개일 때 수행 속도와 MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.

    clock_t st,et;

 

    MakeRandomMembers(base,MAX_DATA);

    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;

    st = clock();   

    insertion_sort(base,MAX_DATA,CompareByName);   

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA);

 

    MakeRandomMembers(base,MAX_DATA/10);

    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;

    st = clock();

    MakeRandomMembers(base,MAX_DATA/10);

    insertion_sort(base,MAX_DATA/10,CompareByName);

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA/10);

    return 0;

}

 

다음은 실행 결과예요.

▷실행 결과

정렬 전

0000757147,이름0167851000

0301413356,이름0336971124

0659598368,이름0160567225

0391749387,이름0004890851

0035766290,이름0026239572

0473038164,이름0000597006

0003615544,이름0326051436

0392289610,이름0118341522

0170427798,이름0037215528

0675016433,이름0168544290

번호로 정렬 후

0000757147,이름0167851000

0003615544,이름0326051436

0035766290,이름0026239572

0170427798,이름0037215528

0301413356,이름0336971124

0391749387,이름0004890851

0392289610,이름0118341522

0473038164,이름0000597006

0659598368,이름0160567225

0675016433,이름0168544290

이름으로 정렬 후

0473038164,이름0000597006

0391749387,이름0004890851

0035766290,이름0026239572

0170427798,이름0037215528

0392289610,이름0118341522

0659598368,이름0160567225

0000757147,이름0167851000

0675016433,이름0168544290

0003615544,이름0326051436

0301413356,이름0336971124

수행 성능 테스트1 자료 개수:1000

수행 속도:1560

수행 성능 테스트2 자료 개수:100

수행 속도:31

 

삽입 정렬도 결과를 보면 자료 개수가 MAX_DATA일 때 MAX_DATA/10일 때보다 100배 정도 느린 것을 알 수 있습니다. 앞에서 알고리즘 성능을 분석할 때 O(n^2)와 비슷하죠. 그렇지만 내부 반복문을 탈출하는 조건이 있어서 앞의 세(순차, 거품, 선택) 가지 정렬 알고리즘보다 빠른 것을 알 수 있어요.