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

  • 20 minutes to read

선택 정렬(Selection Sort) 알고리즘은 데이터 중 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 위치를 바꾸는 과정을 반복하여 정렬하는 방식입니다. 데이터의 개수가 n개일 경우, 전체 반복 횟수는 n - 1번입니다. 오름차순 기준으로 배열을 정렬할 때, 선택 정렬은 배열의 처음부터 가장 작은 데이터를 차례대로 채워 나갑니다.

반면, 거품 정렬(Bubble Sort) 알고리즘은 오름차순으로 정렬할 때, 연속된 두 데이터를 비교하여 큰 값을 뒤로 이동시키며 가장 큰 값을 오른쪽으로 밀어 정렬하는 방식을 사용합니다.

선택 정렬 회전수

배열 data[5]에 다음과 같이 데이터가 입력되어 있다고 할 때 선택 정렬을 사용해서 오름차 순으로 정렬시키는 단계를 간단히 표현해 보겠습니다. 지면상 모든 단계를 표현하는 게 아닌 왼쪽에 가장 작은 값이 들어올 때까지만 표현합니다.

data[5]

data[0] data[1] data[2] data[3] data[4]
46 32 11 24 55

1회전:

data[0]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복하면 data[0]에는 가장 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
46 32 11 24 55
32 46 11 24 55
11 46 32 24 55

2회전:

data[1]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 2회전이 끝나면 data[1]에 두 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 46 32 24 55
11 32 46 24 55
11 24 46 32 55

3회전:

data[2]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 3회전이 끝나면 data[2]에 세 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 24 46 32 55
11 24 32 46 55

4회전:

data[3]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복합니다. 4회전이 끝나면 data[3]에 네 번째로 작은 값이 들어갑니다.

data[0] data[1] data[2] data[3] data[4]
11 24 32 46 55
11 24 32 46 55

참고: 선택 정렬 관련 정보처리기사 필기 문제

코드를 작성하기 전에 선택 정렬 알고리즘의 흐름을 조금 더 정리하는 차원에서, 정보처리기사 필기 시험에 여러 해에 걸쳐서 출제된 선택 정렬 관련 문제를 참고용으로 풀어보겠습니다.

문제: 자료가 다음과 같이 주어졌을 때 선택 정렬(selection sort)을 적용하여 오름차순으로 정렬할 경우 pass 2를 진행한 후의 정렬된 값으로 옳은 것은?

자료: 9, 4, 5, 11, 8

가. 4, 5, 9, 8, 11		나. 4, 5, 9, 11, 8
다. 4, 5, 8, 11, 9		라. 4, 5, 8, 9, 11

정답: 나

해설: 가장 작은 데이터를 왼쪽으로 하나씩 채우는 형태로 각 회전이 끝난 후의 배열 모양은 다음과 같습니다.

1.	pass 1: 4, 9, 5, 11, 8
2.	pass 2: 4, 5, 9, 11, 8
3.	pass 3: 4, 5, 8, 11, 9
4.	pass 4: 4, 5, 8, 9, 11

선택 정렬 알고리즘 순서도

다음은 선택 정렬로 오름차순으로 정렬할 때의 순서도입니다.

오름차순 정렬

선택 정렬 알고리즘 순서도 1

다음은 선택 정렬로 내림차순으로 정렬할 때의 순서도입니다.

내림차순 정렬

선택 정렬 알고리즘 순서도 2

[실습] 정렬(Sort) 알고리즘 사용하기

주어진 데이터를 오름차순 또는 내림차순으로 정렬하는 정렬 알고리즘 중 가장 학습하기 편한 선택 정렬 알고리즘을 적용해 보겠습니다. 다음 내용을 입력한 후 실행해 보세요. 정렬 알고리즘은 오름차순 기준으로 가장 작은 데이터를 왼쪽으로 순서대로 이동합니다.

예제: 데이터를 순서대로 정렬

다음 예제를 작성 후 실행해 보세요.

selection_sort.c

//[?] 무작위 데이터를 순서대로 [오름차순|내림차순] 정렬
#include <stdio.h>
#define N 5

// 정렬 알고리즘(Sort Algorithm): 가장 [작은|큰] 데이터를 왼쪽으로 순서대로 이동
int main(void)
{
    //[1] Input: Data Structure(Array, List, Stack, Queue, Tree, DB, ...)
    int data[] = { 3, 2, 1, 5, 4 };
    int i, j, temp;

    //[2] Process: Selection Sort(선택 정렬) 알고리즘
    for (i = 0; i < N - 1; i++) // i = 0 to N - 1
    {
        for (j = i + 1; j < N; j++) // j = i + 1 to N
        {
            if (data[i] > data[j]) // 부등호 방향: 오름차순(>), 내림차순(<)
            {
                // 3단계 코드에 의해서 데이터 교환 
                temp = data[i];
                data[i] = data[j];
                data[j] = temp; 
            }
        }
    }

    //[3] Output
    for (int i = 0; i < N; i++)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");

    return 0;
}

1       2       3       4       5

코드: 알고리즘_정렬.c

/*
정렬(Sort) 알고리즘 : 데이터를 순서대로 정렬
*/
#include <stdio.h>

int main(void)
{
    //[1] Input
    int intNum[5] = { 2, 3, 1, 5, 4 };
    int i, j, temp;

    //[2] Process : Selection Sort(선택 정렬)
    for (i = 0; i < 5 - 1; i++)
    {
        for (j = i + 1; j < 5; j++)
        {
            if (intNum[i] > intNum[j])
            {
                temp = intNum[i];
                intNum[i] = intNum[j];
                intNum[j] = temp;
            }
        }
    }

    //[3] Output
    for (i = 0; i < 5; i++)
    {
        printf("%d\n", intNum[i]);
    }

    return 0;
}

함수로 구현한 C 언어 선택 정렬 알고리즘 예제

예제: 선택 정렬 알고리즘

코드: selection_sort.c

#include <stdio.h>

void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int arr[] = {34, 12, 45, 8, 21, 17};
    int size = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, size);

    printf("선택 정렬 후 배열: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

예제: 함수와 포인터를 사용한 선택 정렬 구현

코드: selection_sort.c

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        swap(&arr[min_index], &arr[i]);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

정렬 알고리즘은 실무에서도 자주 활용되는 중요한 알고리즘입니다. 그중에서도 선택 정렬은 기본 중의 기본으로, 반드시 한 번은 익혀야 할 알고리즘입니다. 물론 실제 현업에서는 선택 정렬보다 훨씬 빠른 내장 정렬 함수를 사용합니다. 예를 들어, C 언어에서는 qsort() 함수, C#에서는 Sort() 메서드나 OrderBy()와 같은 LINQ 메서드를 활용하곤 합니다.

요즘처럼 AI 도구가 발전한 시대에는 모든 정렬 알고리즘을 일일이 외울 필요는 없습니다. 하지만 선택 정렬처럼 기본 알고리즘 하나쯤은 거의 암기하다시피 숙지해 두고, 나머지 알고리즘은 ChatGPT 같은 AI 도구의 도움을 받아 구현할 수 있으면 충분합니다.

다만, 코딩 테스트나 학교 시험처럼 암기와 구현 능력을 요구하는 상황에서는 해당 범위의 내용을 확실히 익혀두는 것이 좋습니다.

정리하자면, 현업보다는 학교 수준의 알고리즘 학습이 여전히 암기 중심이라는 점은 아쉽지만, 현실이기도 합니다. 그래서 하나만 외운다면 선택 정렬을 먼저 익히고, 그 외에는 AI를 잘 활용하자는 것이 초보 학습자에게 드리고 싶은 조언입니다.

VisualAcademy Docs의 모든 콘텐츠, 이미지, 동영상의 저작권은 박용준에게 있습니다. 저작권법에 의해 보호를 받는 저작물이므로 무단 전재와 복제를 금합니다. 사이트의 콘텐츠를 복제하여 블로그, 웹사이트 등에 게시할 수 없습니다. 단, 링크와 SNS 공유, Youtube 동영상 공유는 허용합니다. www.VisualAcademy.com
박용준 강사의 모든 동영상 강의는 데브렉에서 독점으로 제공됩니다. www.devlec.com