C Data Structure - 선택 정렬

 

오늘도 짤막하게 코딩해보고 바로 포스팅한다. 이렇게 하니 매우 여유있게 보고 정리할 수 있는 것 같아서 좋다.
선택 정렬 또한 간단하다 ㅋ

선택 정렬이란?

예시임

위와 같은 배열이 있다. 이를 오름차순으로 정렬할 예정이다.

버블 정렬이 이전 요소들 앞뒤를 비교해가면서 결국, 맨 마지막 대상을 확정 짓는 것이라면 선택 정렬은 반대이다.

맨 왼쪽 요소를 확정 지어가면서 범위를 좁혀나가는 것인데, 버블 정렬처럼 비교한 후 더 변경할 조건이 맞는 경우 값을 교환하는 것이 아니라 변경할 '인덱스'를 저장해 둔 후, 자리를 확정 지을 때 이 인덱스를 활용하여 교환을 한다.

일련의 프로세스 정리

!! 수정 !! :: 3번 동그라미에서 1(인덱스 2)는 1(인덱스 3)로 변경되어야 합니다!!!!!!!!!!!!!!!!!!!!!

코드 및 실행 결과

----

#include <stdio.h>
 
void SelectSort(int arr[], int n)
{
    int min_index = -1;
    int temp = -1;
 
    int i = 0, j = 0;
    for (i = 0; i < n-1; i++) // 마지막에서 -1 인덱스까지만 확정 지으면 나머지 하나는 자동 확정~
    {
        min_index = i; // 오름차순이라는 가정 하에, 가장 작은 값이 존재하는 인덱스
        for (j = i+1; j < n; j++) // 확정 지을 자리를 비교할 필요가 없으므로 i + 1
        {
            if (arr[min_index] > arr[j])
                min_index = j;
        }
        temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
    return;
}
 
int main(void)
{
    int i = 0;
    int arr[4] = { 5, 9, 3, 1 };
    SelectSort(arr, sizeof(arr) / sizeof(int));
    
    for (i = 0; i < 4; i++)
        printf("%d, ", arr[i]);
    fputc('\n', stdout);
    return 0;
}

9번 라인에서 i의 조건을 n-1 미만으로 두는 이유를 다음 그림을 통해서 설명하겠다.

 

----

 

 

선택 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : n-1 회 무조건 대입이 일어난다. -> O(n)

버블 정렬에 비하면 양호하지만 버블 정렬에서는 최선의 경우에는 한 번도 대입 연산이 없을 수 있으므로, 비교하기 난감할 뿐이다.