4. 선택 정렬(Selection Sort)

선택 정렬의 개념

한 위치씩 선택해서 순차적으로 작은 값들을 찾아서 선택 정렬이라고 한다.

 

▼ 선택 정렬 알고리즘 도식화

선택 정렬은 최소값을 찾은 다음 교환하기 때문에 교환 함수 호출을 최소화할 수 있다.

선택 정렬의 성능[O(n²)]

정렬할 자료의 수의 제곱에 비례하여 늘어난다.

 

C99

▼ 관련 개념

Loop & Pointer & Call By Address

 

▼ 구현 코드

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

void SelectionSort(int arr[], int length)
{
    int min;

    for (int i = 0; i < length - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(arr[j], arr[min]) < 0)
            {
                min = j;
            }
        }
        Swap(&arr[min], &arr[i]);
    }
}

내부 순환문 밖에 Swap() 함수를 호출하고 있다는 것이 중요하다.

 

남은 배열 값중 최솟값이 저장된 위치만 저장해서 교환하기 때문에 데이터의 양이 적을 때 속도가 빠르다.

문제는 이 데이터의 양이 적다는 기준이 100개 까지라서 실무에서 쓰기엔 느린 정렬 방법이다.

CPP B.11

▼ 관련 개념

Loop & STD

 

▼ 구현 코드

#include <algorithm>

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void SelectionSort(int arr[], int length)
{
    int min;

    for (int i = 0; i < length - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(arr[j], arr[min]) < 0)
            {
                min = j;
            }
        }
        std::swap(arr[min], arr[i]);
    }
}

CPP A.98 <algorithm> 라이브러리를 사용한 방법이다.

CPP A.11

▼ 관련 개념

Loop & Template & STD

 

▼ 구현 코드

template<typename T>
int Compare(T lhs, T rhs)
{
    return (lhs - rhs);
}

template<typename T, typename L>
void selectionSort(T arr[], L length)
{
    int min;

    for (int i = 0; i < length - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(arr[j], arr[min]) < 0)
            {
                min = j;
            }
        }
        std::swap(arr[min], arr[i]);
    }
}

주조(Template)를 사용하여 어떤 변수형이 오더라도 비교하고 정렬할 수 있는 코드가 되었다.

배열의 길이가 int형이 아닌 long이나 long long으로 오더라도 문제없이 작동한다.

 

CPP A.11에서는 std::swap 함수가 <utility>로 이동했다.