삽입 정렬 - 1

크기가 작은 정렬에 효율적인 삽입 정렬을 이용해 정렬 문제를 풀기위해 문제를 다음과 같이 정의한다. 

 

정렬하고자 하는 숫자를 key라고 한다. 그리고 원소가 n개인 배열을 입력으로 준다.

 

아래는 그림으로 삽입 정렬을 표현 한 것이다.

입력은 1부터 6까지 임의으로 섞여 있는 배열  A = {5,  2,  4,  6,  1,  3}이다. 

그림은 배열  A = {5,  2,  4,  6,  1,  3}이고

배열의 index는 각 0  1   2   3  4   5이다. 

주황색 사각형은 key값이고, 오른쪽으로 비교하기 시작한다.

 

(d)를 예시로 둔다면

 2 4 5 6 1 3

1. 6과 비교 (1이 작음)

2. 5와 비교 (1이 작음)

3. 4와 비교 (1이 작음)

4. 2와 비교 (1이 작음)

 

그 후 해당하는 index에 key에 해당하는 값을 넣고 key값을 이동시킨다.

 1 2 4 5 6 3 

 

아래는 그림을 C++ 로 구현한 내용이다. 

#include <iostream>

using namespace std;

int main(void)
{
    int A[] = {5,2,4,6,1,3};    //index값은 0부터 시작한다. (A[0] = 5, A[1] = 2, A[2] = 3)
    int key, comp;
    
    int lengthA= sizeof(A)/sizeof(A[0]); //sizeof는 요소의 byte수를 리턴


    for(int index = 1; index <lengthA; index++){
        key = A[index]; //  A[index]값을 저장한다.

        comp = index-1; 
        if(index == 1){
            if(key < A[comp]){
                A[index] = A[comp];
                A[0] = key;
            }

        }else{
            while(comp >=0){
                if(key < A[comp]){           // A[comp] 가 key값보다 작다면
                    A[comp+1] = A[comp];      // 오른쪽으로 한칸 미는 작업이다. key값이 들어갈 자리를 확보하기 위해서이다.
                }else{
                    A[comp+1] = key;
                    break;       
                }if(comp == 0){ //A[comp]가 0. 즉, 모든 수가 key 값보다 크다면
                    A[0] = key; 
                    
                }
                comp--;
            }   
        }
    }
    
    for(int n = 0; n<lengthA; n++)
        cout<<A[n]<<" ";

    return 0;
}

 

 

아래의 그림은 C++ 코드를 설명했다. 

1. index = 1, comp = 0, key = 2 = A[index]

> key < A[comp], 2<5 이므로

A[index] = A[comp] // A[index]에 A[comp]값을 넣는다. 오른쪽으로 숫자를 밀기 위함이다. 

> comp 값이 0이므로 

A[0] = key  // A[0]에 key값을 넣는다. 

 

>key값이 들어왔으므로 index에 1을 더해준다. 

 

2. index = 2, comp = 1, key = 4 = A[index]

> key < A[comp], 4<5 이므로

A[com+1] = A[comp]

> 비교가 끝났으므로 comp값을 1감소시킨다.

comp = 0

 

> key > A[comp], 4>2 이므로

A[comp+1] = key

>key값이 들어왔으므로 index에 1을 더해준다. 

 

3. index = 3, comp = 2, key = 6 = A[index]

> key > A[comp] 이므로, key값을 고정한다. 

A[comp+1] = key

 

>key값이 들어왔으므로 index에 1을 더해준다. 

 

아래의 보기부터는 같은 내용이므로 그림만 삽입하였다. 

4. index = 4, comp = 3, key = 1 = A[index]

 

5. index = 4, comp = 3, key = 1 = A[index]

 

아래는 내림차순으로 정렬하는 코드를 C++ 로 구현한 내용이다. 

원리는 위와 같다.

#include <iostream>

using namespace std;
int length(int A); //배열 A의 사이즈를 구하는 함수

int main(void)
{
    int A[] = {5,2,4,6,1,3};    //index값은 0부터 시작한다. (A[0] = 5, A[1] = 2, A[2] = 3)
    int key, comp;
    
    int lengthA= sizeof(A)/sizeof(A[0]); //sizeof는 요소의 byte수를 리턴


    for(int index = 1; index <lengthA; index++){
        key = A[index]; //  A[index]값을 저장한다.

        comp = index-1; 
        if(index == 1){
            if(key > A[comp]){
                A[index] = A[comp];
                A[0] = key;
            }

        }else{
            while(comp >=0){
                if(key > A[comp]){           // A[comp] 가 key값보다 작다면
                    A[comp+1] = A[comp];      // 오른쪽으로 한칸 미는 작업이다. key값이 들어갈 자리를 확보하기 위해서이다.
                }else{
                    A[comp+1] = key;
                    break;       
                }if(comp == 0){ //A[comp]가 0. 즉, 모든 수가 key 값보다 크다면
                    A[0] = key; 
                    
                }
                comp--;
            }   
        }
    }
    
    for(int n = 0; n<lengthA; n++)
        cout<<A[n]<<" ";

    return 0;
}

 

참고로 C++ 에서 <algorithm> 헤더파일은 아래와 같이 sort 알고리즘을 지원한다.

 

sort(A[start],A[end]):  [start, end) 의 범위에 있는 인자를 오름차순으로 정렬해주는 함수이다.

> quick sort(퀵 정렬)을 기반으로 함수가 구현되어있다.