삽입정렬 (Insertion sort)

삽입정렬 (Insertion sort)

리스트를 가상으로 왼쪽과 오른쪽 리스트로 구분하자.

왼쪽은 정렬이 되어있고, 오른쪽은 정렬해야될 값이 들어있다.

오른쪽 리스트에 첫 번째 값이 왼쪽 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후 제 위치에 삽입한다.

이 경우, 삽입될 위치로부터 오른쪽에 있는 값들을 한 칸씩 오른쪽으로 이동시킨다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

※ 유의사항

- 삽입정렬은 영역을 정하고 그 영역 안에서의 순서를 정해 이동하는 방식이다.

- value : 현재 기준이 되는 값. 또는 값의 임시 저장소라고 생각하면 된다.

시작 : 7 3 9 4 1

1).

 value  : 3

              ↓

인덱스 :   0 1 2 3 4

   값    : [7 3] 9 4 1 

3을 기준으로 7을 비교한다.

if( 3 < 7 ) ? 참.   

현재 검사하고 있는 범위( [ ] ) 안에서 각 숫자들을 한 칸씩 당겨주어야 하므로.

1번째 인덱스에 0번째 인덱스 값을 넣는다.

      ↓

- [ 7 7 ] 9 4 1 

다음은 비교할 값이 없으므로 현재 인덱스에 value가 가진 값을 대입한다.

    ↓

- [ 3 7 ] 9 4 1 

2).

value  : 9

               ↓

인덱스 :  0 1 2   3 4

인덱스: [ 3 7 9 ] 4 1    

if( 9 < 7 ) ? 거짓.

if문의 조건이 충족되지 않으므로 다음으로 넘어간다.

3).

 value  : 4

                   ↓

인덱스 :    0 1 2 3   4

   값    : [ 3 7 9 4 ] 1 

if( 4 < 9 ) ? 참

1. 숫자들을 뒤로 한 칸씩 당긴다.

2. value의 값과 당길 숫자들과 비교한다.

3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.

        ↓

- [ 3 7 9 4 ] 1  - if( 4 < 9 ) ? 참

=>[ 3 7 9 9 ] 1

      ↓

- [ 3 7 9 9 ] 1  - if( 4 < 7 ) ? 참

=>[ 3 7 7 9 ] 1 

    ↓  

- [ 3 7 9 9 ] 1  - if( 4 < 3 ) ? 거짓

=>[ 3 4 7 9 ] 1 

4).

 value  : 1

                      ↓

인덱스 :    0 1 2 3 4

   값    : [ 7 3 4 9 1 ]

if( 1 < 9 ) ? 참

1. 숫자들을 뒤로 한 칸씩 당긴다.

2. value의 값과 당길 숫자들과 비교한다.

3. 당길 숫자가 value의 값보다 더 작다면 현재 인덱스의 + 1칸에 value값을 대입한다.

              ↓

-    [ 3 4 7 9 1 ]  - if( 1 < 9 ) ? 참

=>   [ 3 4 7 9 9 ]

           ↓

-   [ 3 4 7 9 9 ]  - if( 1 < 7 ) ? 참

=>  [ 3 4 7 7 9 ]

        ↓

-   [ 3 4 7 9 9 ]  - if( 1 < 4 ) ? 참

=>  [ 3 4 4 7 9 ]

      ↓

-   [ 3 4 7 9 9 ]  - if( 1 < 3 ) ? 참

=>  [ 3 3 4 7 9 ]

더이상 검사할 인덱스가 없으므로 현재 인덱스에 vaule를 대입.

=> [ 1 3 4 7 9 ]

Code

#include <iostream>
using namespace std;
 
#define MAX            5
 
void InsertSort(int *Number );
void main()
{
    int Number[MAX] = {7, 3, 9, 4, 1};
 
    InsertSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void InsertSort( int *Number )
{
    int Value,i,j;
    for(i = 1; i < MAX; i++)
    {
        Value = Number[i];
        for(j = i - 1; j >= 0; j--)
        {
            if(Value < Number[j])
                Number[j + 1] = Number[j];
            else
                break;
        }
        Number[j + 1] = Value;
    }
}

결과