[알고리즘] 정렬 - 선택 정렬, O(N^2)

  선택 정렬(Selection Sort)은 알고리즘 효율이 낮은 정렬 알고리즘 중 하나이다. 선택 정렬에서 "선택"이라는 것은 여러 개의 데이터 중 특정 순서에 있는 데이터를 구하는 동작이다. 예컨대 최댓값, 최솟값 또는 i 번째로 큰 데이터 등을 얻는 것이 "선택"이다. 그래서 선택 정렬은 데이터 중 최댓값을 계속 한 쪽으로 몰아넣으면서 정렬하는 방식이다.

 

    선택 정렬 (Selection Sort) 개념 소개              

 

1.   처음부터 차례대로 비교하며 데이터 전체 중 최댓값을 찾는다.
2.   최댓값과 가장 마지막에 위치한 값을 swap 한다.
3.   가장 마지막을 제외한 데이터에 대해 1, 2번을 반복한다.

 

  선택 정렬은 아이디어 자체는 간단하지만 어떠한 경우에서도 Θ(N^2)의 효율을 보인다.선택 정렬 알고리즘은 처음부터 차례대로 비교하며 데이터 전체 중 최댓값을 찾는다. 정렬되어 있다는 정보를 알지 못하므로 결국 N-1번 비교한 후 최댓값을 찾아 마지막 원소와 swap한다. 같은 과정을 데이터가 한 개 제외된 상태에서 반복하므로 N-2번 비교가 발생한다. 결국 비교 횟수가 1번씩 감소하여 비교횟수가 1까지 감소한다. 즉, 총 (N-1) + (N-2) + ... + 1 = (N-1)*N/2 회 비교가 발생한다. 이러한 과정이 현재 배열 상태에 전혀 상관없이 일어나므로 비교횟수는 항상 일정하다. 예를 들어 정렬된 데이터여도, 역순으로 정렬된 데이터여도 비교횟수는 동일하게 Θ(N^2)의 시간 복잡도를 나타낸다. 이러한 점에서 앞으로 정리할 모든 정렬 중에 가장 비효율 적인 알고리즘이 되겠다.

 

    C++ 구현              

#include <iostream>

void SelectionSort(int* _arr, int _size)
{
    // 비교횟수를 1씩 감소시킴.
    for (int i = _size; i > 0; --i)
    {
        int maxIndex = 0;
        // 인덱스 1씩 올라가면서 차례대로 비교한다.
        for (int j = 1; j < i; ++j)
        {
            // 최댓값 지닌 인덱스 갱신
            if (_arr[j] > _arr[maxIndex])
            {
                maxIndex = j;
            }
        }

        // 최댓값과 마지막 원소 swap
        int temp = _arr[maxIndex];
        _arr[maxIndex] = _arr[i-1];
        _arr[i - 1] = temp;
    }
}

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

    return 0;
}

 

 

   같은 알고리즘을 매 번 구현할 때 마다 새로운 점이 신기하다.. 알고리즘 동작 방식만 기억나고 매번 구현할 때마다 연습이 되니 어쩌면 재능일지도..