정렬 - 선택정렬(Selection Sort)

선택정렬(Selection Sort)

 

지금부터는 다양한 종류의 알고리즘에 대해서 알아보도록 할 것입니다. 알고리즘의 종류는 매우 다양하지만 그 중에서 가장 많이 알려져있는 정렬에 대해서 차근차근 알아보겠습니다.

 

정렬에는 종류가 다양한데 그 중 가장 기본적인 것은 선택정렬입니다. 1~10까지의 숫자가 무작위로 있을 때 오름차순으로 정렬하는 것을 예시로 많이 사용하여 각 알고리즘의 동작과정을 살펴보는 것이 보편적입니다.

 

선택정렬은 "가장 작은 것을 선택하여 앞으로 보내는 방법" 입니다. 

#include <iostream>
using namespace std;

int main() {
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    int n = 10, minIndex, temp;

    for (int i = 0; i < n; i++) {
        int min = 9999; // 임의로 큰 값 설정
        for (int j = i; j < n; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

 

위 소스코드는 C++로 표현한 오름차순 선택정렬 입니다. 위 과정을 5단계로 나눠서 간단하게 설명하면 다음과 같습니다.

 

1. 배열 arr에 정렬할 데이터를 저장한다.

2. 현재 위치(i)부터 끝까지 순회하며 최솟값을 찾는다.
3. 찾은 최솟값을 현재 위치(i)와 교환한다.
4. 배열이 정렬될 때까지 2~3단계를 반복한다.
5. 정렬된 결과를 출력한다.

 

실제로 숫자를 대입하며 실행과정을 따라가다 보면, 배열의 인덱스 앞에서부터 하나씩 최솟값으로 채워집니다. 위 과정을 보면 아시겠지만, 선택정렬에서 중요한 것은 최소값을 찾고, 적절한 인덱스 위치와 교환하는 것이 핵심입니다. 그렇다면 위 코드에서 오름차순이 아닌 내림차순으로 정렬하려면 어떤 부분을 바꿔야 할까요?

 

정답은 if (min > arr[j]) 부분의 부등호를 반대로 if (min < arr[j]) 이렇게 바꿔주면 내림차순 정렬이 됩니다. 그리고 변수의 뜻이 어긋나기 때문에 min대신 max로 바꿔주면 더 좋을 것 같습니다.

 

선택정렬의 특징

시간 복잡도 : O(n^2)

=> 리스트 크기가 n일 때, n번 반복하며 각 단계에서 남은 리스트에서 최소값을 찾는 데 다시 n번의 비교가 필요하기 때문입니다.

공간 복잡도 : O(1)

=> 기존 리스트 내에서 교환을 통해 정렬을 수행하므로 별도의 메모리를 거의 사용하지 않습니다.

안정성 : 불안정 정렬

=> 동일한 값의 원소들이 처음의 순서를 유지하지 못할 수 있기 때문입니다.

 

장단점

장점

- 구현이 간단하고 직관적이다.

- 비교 횟수가 일정하여, 자료가 적을 때는 성능에 큰 문제가 없다.

 

단점

- 시간 복잡도가 크기 때문에, 자료의 양이 많을 때는 비효율적이다.

- 다른 정렬 알고리즘에 비해 상대적으로 느리다.

 

선택정렬의 시간 복잡도를 과정으로 분리해서 살펴보면 비교횟수와 교환횟수로 나눌 수 있습니다. 비교횟수는 O(n^2) 교환횟수는 O(n)이므로, 전체 시간 복잡도는 O(N^2)입니다.

 

선택정렬의 활용

선택정렬의 장단점을 봤을 때, 선택정렬을 활용할 수 있는 분야를 알 수 있습니다. 첫번째로, 적은 데이터를 가지는 환경에서 사용하기 좋습니다. 두번째로 선택정렬은 제자리 정렬 방식이기 때문에, 메모리가 제한된 환경에서 사용하기 좋습니다. 마지막으로 학생 성적 3등까지와 같은 상위/하위의 일부 데이터를 찾을 때 유용합니다.

 

결론적으로 선택정렬은 대규모 데이터에서는 비효율적이지만, 작은 데이터 정렬, 메모리 제한 환경, 특정 개수만 정렬하는 경우 등에 적절하게 활용할 수 있습니다.

 

NEXT

오늘은 알고리즘의 기본인 정렬, 그 중에서도 선택정렬을 알아보았습니다. 다음에는 정렬 시리즈를 쭉 이어서 버블정렬을 알아보도록 하겠습니다. 감사합니다.