선택 정렬(selection sort)

이번 시간에는 가장 이해하기 쉬운 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보겠다. 선택 정렬 알고리즘은 구현하기 굉장히 단순하지만 정렬시 많은 시간이 걸리는 비효율적인 방법이다.

 

선택 정렬?

선택 정렬 알고리즘이 어떻게 동작하는지 살펴보자. 먼저 정렬되지 않은 숫자들이 들어 있는 리스트와 정렬이 완료된 숫자들이 들어가는 리스트가 있다고 하자. 아래 그림과 같이 초기 상태에서 정렬된 리스트는 비어 있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어 있다. 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 이것은 오른쪽 리스트가 공백 상태가 될 때까지 되풀이 된다.

선택 정렬의 원리

위 설명에서는 두 개의 리스트로 나누어 설명했지만 실제로 선택 정렬을 구현하기 위해 두 개의 배열을 사용할 필요는 없다. 아래 그림과 같이 정렬이 안 된 리스트에서 최솟값이 선택되면 이 값을 배열의 첫 번째 요소과 교환한다. 이렇게 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 제자리 정렬(in-place sorting)이라고 한다. 최솟값 1과 첫 번째 요소 5를 교환하면 전체 배열은 정렬된 부분과 되지 않은 부분으로 나뉜다. 다음에는 두 번째 요소부터 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1)만큼 되풀이하면 추가적인 배열을 사용하지 않고서도 전체 숫자들이 정렬된다.

 

선택 정렬의 과정

선택 정렬 알고리즘 구현

#include<iostream>
 
using namespace std;
 
inline void swap(int& x, int& y)
{
    int t = x;
    x = y;
    y = t;
}
 
void selectionSort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int least = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[least])
                least = j;
        }
        swap(a[i], a[least]);
    }
}
 
int main()
{
    int arr[] = { 5,3,8,1,2,7 };
 
    for (int i = 0; i < 6; i++)
        cout << arr[i] << " ";
    cout << endl;
 
    selectionSort(arr, 6);
 
    for (int i = 0; i < 6; i++)
        cout << arr[i] << " ";
    cout << endl;
 
    return 0;
}

선택 정렬의 시간 복잡도 분석

선택 정렬의 성능 분석을 위하여 비교횟수와 이동횟수를 따로 구해보자. 

먼저 비교횟수를 구하기 위하여 두 개의 for 로프의 실행횟수를 계산해보자. 외부 루프는 n-1번 반복한다. 내부 루프는 0에서 n-2까지 변하는 i에 대하여 (n-1)-i번 반복한다. 키값들의 비교가 내부 루프 안에서 이루어지므로 전체 비교횟수는 다음과 같이 된다.

레코드 교환은 외부 루프의 실행횟수만큼 이루어지고, 한번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동횟수는 3(n-1)이 된다.

 

선택 정렬의 장점은 자료 이동 횟수가 미리 결정된다는 점이다. 그러나 전체 시간 복잡도가 O(n^2)이므로 효율적인 알고리즘은 아니다. 또 하나의 문제점은 안정성을 만족하지는 않는다는 점이다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. 그러나 알고리즘이 매우 간단하다는 장점이 있다.