[정렬 알고리즘]Insert Sorting - 삽입정렬

삽입정렬은 정렬된 자료범위에서 자신의 위치를 찾아가는것을 반복하며 정렬해가는 알고리즘입니다. 삽입정렬은 BigO(n^2)의 시간이 걸립니다.

삽입정렬은 다음과 같은 순서로 차례차례 정렬을 합니다

위의 과정을 프로그래밍으로 나타내면 다음과 같이 됩니다.

#include<iostream>
 
void Print(int TargetArray[], int Length)            //출력용 함수
{
    for (int i = 0; i < Length; i++)
        std::cout << TargetArray[i] << " ";
    std::cout << std::endl;
}
 
void Swap(int *Target_Left, int *Target_Right)        //값 교체용 함수
{
    int Temp;
    Temp = *Target_Right;
    *Target_Right = *Target_Left;
    *Target_Left = Temp;
}
 
void InsertSorting(int *TargetArray, int  Length)                    //삽입정렬
{
    int Count = 0;
    for (int i = 1; i < Length; i++)                                //1pass
    {
        Count = i;
        while (Count >= 0)
        {
            if (TargetArray[Count - 1] > TargetArray[Count])            //자신의 자리를 찾으면 교체
                Swap(&TargetArray[Count - 1], &TargetArray[Count]);
            Count--;
        }
        Print(TargetArray, Length);
    }
}
 
void main()
{
    int Array[] = { 9,7,5,3,1 };
    InsertSorting(Array, 5);
    std::cout << "최종 결과 : ";
    Print(Array, 5);
}

결과는 다음과 같이 나옵니다.