[정렬 알고리즘]Select Sorting - 선택정렬

선택 정렬은 다음과 같은 과정을 거치며 정렬을 해가는 정렬알고리즘입니다. 선택정렬은 BigO(n^2)의 시간이 걸립니다.

1. 주어진 데이터들 중에서 가장 작은 데이터를 찾는다
   
   
2. 정렬되지 않는 값들 중에 가장 앞에 있는 데이터와 교체한다
   
   
3. 정렬된 값들을 제외하고 나머지에 대하여 정렬이 끝날때 까지 반복한다.

선택정렬의 과정을 애니메이션으로 나타내면 다음과 같이 진행이 됩니다.

정렬된 대상을 제외한 값들에 대해서 최소값을 찾은 뒤 교체하는 과정의 반복입니다. 위의 반복을 프로그래밍으로 표현하면 다음과 같이 됩니다.

#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 SelectSorting(int *TargetArray, int Length)            //선택정렬
{
    int MinimumPosition = 0;
    int InsertPosition = 0;
 
    for (int pass = 0; pass < Length - 1; pass++)                //1pass
    {
        MinimumPosition = InsertPosition;                        //정렬되지 않은 값들중 제일 앞에는 우선 최소도 둔다
        for (int i = InsertPosition + 1; i < Length; i++)    
        {
            if (TargetArray[i] < TargetArray[MinimumPosition])    //최소 값을 발견하면 그 위치를 기억한다
                MinimumPosition = i;
        }
        Print(TargetArray, Length);
        Swap(&TargetArray[MinimumPosition],&TargetArray[InsertPosition]);    //한 패스가 끝나면 제일 작은 위치와 정렬되지 않은 값들의 제일앞과 교체한다
        InsertPosition++;
    }
}
 
void main()
{
    int Array[] = { 3,1,9,5,7 };
    SelectSorting(Array, 5);
    std::cout<<"최종 결과 : ";
    Print(Array, 5);
}

결과는 다음과 같이 나오게 됩니다