[자료구조] 선택정렬

선택 정렬의 이해

선택 정렬은 버블 정렬보다 쉬운 알고리즘이다.
하지만 역시 쉬운 만큼 성능이 별로다.

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 맨 앞으로 보내는 방식의 정렬이다.

선택 정렬의 구현

void SelSort(int arr[], int n)
{
    int i, j;
    int maxIdx;
    int temp;

    for(i = 0; i < n-1; i++)
    {
        maxIdx = i;

        for(j = i + 1; j < n; j++)
        {
            if(arr[j] > arr[maxIdx])
            {
                maxIdx = j;
            }
        }

        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}

안쪽 for문

안쪽 for문에서는 정렬의 우선순위가 가장 높은 인덱스를 돌면서 찾는다.

바깥 for문

안쪽 for문에서 찾은 최대 인덱스를 참조해서 맨 앞으로 보내는 스왑 연산을 진행한다.

선택 정렬의 성능 평가

선택 정렬은 빅-오 O(N^2)이다...
바람직한 성능은 아니다.