[알고리즘] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란

간단하게 얘기하자면 배열에서 가장 작은 것이나 가장 큰 것을 찾아 앞으로 보내는 정렬 방법이다.

선택정렬

이미지와 같이 정렬되지 않은 데이터 중에서 최솟값을 찾아 앞으로 보내준다.

시간 복잡도를 계산해보면 배열의 인덱스 개수가 n 개라고 했을 때 O(n^2)이 나온다. 그래프에서는 청록색이다.

따라서 n의 값이 커질수록 걸리는 시간이 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘이다.

 

<C언어 코드>

#include <stdio.h>
 
void SelectionSort(int data[], int size)
{
    int minNum, temp, index = 0;
    int arrSize = size;
    for (int i = 0; i < arrSize; i++)
    {
        //정렬을 0번 인덱스부터 할것이므로 두번째 for문을 i번째부터 시작한다.
        for (int j = i; j < arrSize; j++)
        {
            //검사 시작할 때 최솟값과 인덱스를 검사하는 첫번째 숫자로 정해준다.
            if (j == i)
            {
                minNum = data[j];
                index = j;
            }
            //검사 도중에 최솟값보다 작거나 같은 숫자가 발견되면 인덱스와 최솟값을 바꿔준다.
            if (data[j] <= minNum)
            {
                minNum = data[j];
                index = j;
            }
        }
        //검사가 끝나고 최솟값이 들어있는 인덱스와 정렬된 곳 다음 인덱스와 스왑해줌
        temp = data[i];
        data[i] = data[index];
        data[index] = temp;
    }
}
 
int main()
{
    int arr[10] = { 1, 5, 7, 9, 2, 3, 6, 4, 0, 8 };
    SelectionSort(arr, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}