[알고리즘] 삽입 정렬 알고리즘

안녕하세요.

오늘은 삽입 정렬 알고리즘에 대해 알아보도록 하겠습니다.

 

삽입 정렬 알고리즘

데이터를 정렬 위치에 맞게 삽입하면서 정렬하는 알고리즘

 

구현 방법

오름차순 기준으로 설명하겠습니다.
두 번째 데이터부터 첫 번째 데이터랑 비교 후 두 번째 데이터가 작다면, 두 값을 스왑 하고,
세 번째 데이터를 첫 번째, 두 번째와 비교 후 세 번째 데이터보다 큰 값이 있다면 값이 하나씩 뒤로 밀리게 됩니다.
이것을 반복합니다.

 

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있다면, 다음과 같이 정렬이 되게 됩니다.

첫 번째 회전
두번째 데이터 arrData[1](20)를 임시 변수에 저장합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 20이 첫 번째 데이터인 arrData[0](100)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
그리고 임시 변수에 저장한 값을 arrData[0]에 저장합니다. (20, 100, 10, 12, 5)

두 번째 회전
세 번째 데이터 arrData[2](10)를 임시 변수에 저장합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시변수 데이터인 10이 두 번째 데이터인 arrData[1](100)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 10이 두 번째 데이터인 arrData[0](20)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
그리고 임시 변수에 저장한 값을 arrData[0]에 저장합니다. (10, 20, 100, 12, 5)

세 번째 회전
네 번째 데이터 arrData[3](12)를 임시 변수에 저장합니다.
임시 변수와 세 번째 데이터와 비교하면, 임시 변수 데이터인 12가 세 번째 데이터인 arrData[2](100)보다 작기 때문에 arrData[2]을 arrData[3]로 이동합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시 변수 데이터인 12가 두 번째 데이터인 arrData[1](20)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 12가 첫 번째 데이터인 arrData[0](10)보다 크기 때문에 이동을 멈춥니다.
임시 변수에 저장한 값을 arrData[1]에 저장합니다. (10, 12, 20, 100, 5)

네 번째 회전
다섯 번째 데이터 arrData[4](5)를 임시 변수에 저장합니다.
임시 변수와 네 번째 데이터와 비교하면, 임시 변수 데이터인 5가 네 번째 데이터인 arrData[3](100)보다 작기 때문에 arrData[3]을 arrData[4]로 이동합니다.
임시 변수와 세 번째 데이터와 비교하면, 임시 변수 데이터인 5가 세 번째 데이터인 arrData[2](20)보다 작기 때문에 arrData[2]을 arrData[3]로 이동합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시 변수 데이터인 5가 두 번째 데이터인 arrData[1](12)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 5가 첫 번째 데이터인 arrData[0](10)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
임시 변수에 저장한 값을 arrData[0]에 저장합니다. (5, 10, 12, 20, 100)

 

C++ 코드로 구현

#include <iostream>
using namespace std;
 
void main()
{
    int arrData[5] = { 100, 20, 10, 12, 5 };
    int nTemp;
    int nIndex;
    int nSize = sizeof(arrData) / sizeof(int);
    int j;
    cout << "before : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
 
    for( int i = 1; i < nSize ; i++ )
    {
        nTemp = arrData[i];
        for( j = i; j > 0; j-- )
        {
            if( nTemp < arrData[j-1] )
            {
                arrData[j] = arrData[j-1];
                if( j == 1 )
                {
                    arrData[j-1] = nTemp;
                    break;
                }
            }
            else
            {
                arrData[j] = nTemp;
                break;
            }
            
        }
        
    }
    cout << "after : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
}