[ 정렬 ] 선택 정렬 (Selection Sort) (C++)

이번 글에서는 Selection Sort(선택정렬)에 대해서 다뤄보고자 한다.

선택정렬의 동작원리는 다음과 같다.

가장 먼저 제일 앞에 값을 '최소값을 가진 Index' 라고 가정을 하고 탐색을 시작한다.

탐색 진행 중, 만약 '최소값을 가진 Index'보다 더 작은 값을 가진 값이 나오게 되면, '최소값을 가진 Index'를 더 작은 값을

가진 Index번호로 바꿔준다. 이 과정을 N-1번까지 진행한다.

이후에, 제일 앞Index 번호와,  '최소값을 가진 Index'번호가 다르다면 swap을 해주면 되는 방식이다.

글 보다는 그림으로 이해해보자.

위의 그림이 선택정렬을 1회전 시켰을 때의 결과값이다.

그렇다면 2회전 시킬 때 시작점을 어디로 잡으면될까? 바로, 1번으로 시작하면 된다. 왜냐하면 0번에는 이미 최소값이

자기 자리를 찾아서 정렬되어 있기 때문에 더 이상 관리할 필요가 없기 때문이다.

코드를 보자면 다음과 같다.

void Selection_Sort()                // 선택정렬 함수

{

for(int i = 0 ; i < MAX; i++)   // 0부터 끝까지 전체탐색

{

int Min_Index = i;            // 가장 작은 값이 저장된 Index를 탐색을 시작하는 Index로 가정하고 탐색시작.

for(int j = i  + 1; i j < MAX; j++)    // i + 1번부터 끝까지 탐색을 하는데

{

if(Arr[j] < Arr[Min_Index]) Min_Index = j;    // 만약 더 작은 값이 나오면 Min_Index값 변경

}

if(i != Min_Index) swap(Arr[i], Arr[Min_Index]);    // 만약 변화가 있었다면 swap.

}

}

# 시간복잡도

- 선택정렬의 경우, 가장 처음에 총 N - 1번의 탐색을 하게 된다.

  2회전 때는 정렬된 가장 첫번째 값(최소값)을 빼고 N - 2번 탐색을 하게된다.

  즉, 끝까지 탐색을 하게되면 결과적으로 N - 1 + N - 2 + N - 3 + ... + 1 번 탐색을 하게 된다.

  이를 수식으로 나타나게 되면 총 탐색을 하게 된다.

  빅오 표기법에 의해서 표기하게 되면 번 탐색을 하게 된다.

  그렇다면 최악의 경우와 최선의 경우를 비교해보자.

  최악의 경우는 아마 역방향으로 정렬되어 있는 경우일 것이다.

  즉, 오름차순으로 정렬을 하려고 할 때, { 5, 4, 3, 2, 1 } 순으로 정렬되어 있는 경우를 의미하게 된다.

  이 때, 총 몇번을 탐색해야 될까?? 똑같이 N - 1 + N - 2 + N - 3 + ... +  1번 탐색을 할 것이고 결과적으로 의

  시간복잡도를 갖게 된다.

  최선의 경우는 어떻게 될까? 오름차순으로 정렬할 때 이미 정렬이 되어 있는 경우를 보면 똑같이 의 시간복잡도를

  갖게 될 것이다.

  즉, 선택정렬은 최악의 경우 최선의 경우 상관없이 항상 의 시간복잡도를 갖게 된다.

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<algorithm>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
bool Flag[10000];
 
void Print()
{
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
void Selection_Sort()
{
    for (int i = 0; i < MAX; i++)
    {
        int Min = i;
        for (int j = i + 1; j < MAX; j++)
        {
            if (Arr[j] < Arr[Min]) Min = j;
        }
        
        if (i != Min) swap(Arr[i], Arr[Min]);
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 1; i <= MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    cout << "[ Initialize Array State ]" << endl;
    Print();
    Selection_Sort();
    cout << " [ After Sort Array State ] " << endl;
    Print();
 
    return 0;
}