처음하시는 분들을 위한 C언어 기초강의 시즌2 - 37 [정렬 알고리즘(선택 정렬)]

제 37강) 정렬 알고리즘 - 선택 정렬

오늘은 정렬 알고리즘의 두번째 시간으로 "선택 정렬"에 대해서 알아봅니다.

기본적으로 선택 정렬은 배열에서 사용합니다.

 

선택 정렬이란

 

(사진 출처 : 위키백과 - 선택 정렬)

선택 정렬 또한 버블 정렬과 마찬가지로 성능을 기대하기 어려운 정렬 중 하나입니다.

또한 구현하기도 어렵지 않은 정렬입니다.

매 사이클마다 배열에서 가장 큰 수를 찾습니다.

그렇게 찾은 큰 수를 맨 뒤에서 사이클의 반복횟수만큼 뺀 위치의 원소와 자리를 바꿉니다.

(그 이유는 첫 사이클을 제외한 사이클에서는 맨 뒤에있는 수는 이미 정렬이 끝난 가장 큰 수이기 때문입니다.)

 

사실 위의 과정은 상당히 간략화 되었지만 자세히 들여다 보겠습니다.

선택 정렬은 각 사이클마다 위의 과정처럼 최대 수를 찾아다닙니다.

그리고 맨 뒤(4)에서 해당 사이클의 반복횟수(0)만큼 뺀 위치(4 - 0)의 원소와 자리바꿈을 합니다.

이렇게 되어 선택 정렬의 비교 횟수 또한 T(n) = n(n - 1) / 2 를 성립하게 됩니다.

그리하여 시간 복잡도 O는 O(n(n - 1) / 2) = O(n^2) 이 됩니다.

 

정렬명	시간 복잡도	메모리 사용
선택 정렬	O(n^2)	n

이때 메모리는 기존의 n만큼 할당된 배열 그대로 사용하기 때문에 그대로 n만큼의 메모리를 사용합니다.

이런 부분으로 보아 선택 정렬과 매우 유사하지요?

 

위의 영상은 선택 정렬을 시각적인 춤으로 표현한 좋은 영상입니다.

꼭 보세요.

 

선택 정렬 구현

이제 선택 정렬을 구현하여 봅시다.

어떻게 보면 선택 정렬이 버블 정렬과 같이 구현하기 정말 쉽습니다.

#include <stdio.h>
 
// 배열을 출력하는 함수
void printArr(int* arr, int length)
{
    printf("arr: ");
    for (int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
        if (i + 1 < length)
            printf(", ");
        else
            printf("\n");
    }
    printf("\n");
}
 
// 선택 정렬 함수
void selectionSort(int* arr, int length)
{
    // 처음의 선택된 지점은 초기 지점인 0
    int select = 0;
 
    // 배열의 값을 서로 스왑하기 위한 임시 변수
    int tmp;
 
    // 전체 사이클은 배열의 길이만큼 반복
    for (int i = 0; i < length; i++)
    {
        // 세부 사이클은 배열의 길이에서 현재 사이클만큼 뺀 나머지 만큼 반복
        for (int j = 0; j < length - i; j++)
        {
            // 현재 선택된 위치의 값보다 탐색된 값이 더 크다면
            if (arr[select] < arr[j])
                // 선택지점을 해당 탐색지점으로 바꿈
                select = j;
 
            // 배열의 끝에 도달했을 때
            if (j + 1 == length - i)
            {
                // 선택된 지점의 값과 배열의 길이에서 현재 사이클만큼 뺀 위치의 지점의 값과 바꿈
                tmp = arr[select];
                arr[select] = arr[j];
                arr[j] = tmp;
                select = 0;
            }
        }
    }
}
 
int main(void)
{
    int arr[] = { 9, 11, 8, 2, 3 };
    int length = sizeof(arr) / sizeof(int);
 
    printf("[정렬 전 배열]\n");
    printArr(arr, length);
 
    selectionSort(arr, length);
    printf("[정렬 후 배열]\n");
    printArr(arr, length);
 
    return 0;
}

선택 정렬은 19번 ~ 49번줄 까지입니다.

 

자세한 설명은 소스에 해두었으니 참고하세요.

 

 

 

다음 시간에는

다음 시간에는 삽입 정렬에 대해서 알아봅시다.