알고리즘 선택 정렬(Selection Sort) C언어

▶선택 정렬

버블 정렬과 삽입 정렬보다 횟수가 적어 더 나은 성능을 보여준다.

배열의 앞에서부터 차례대로 정렬이 이루어진다.

평균 성능 시간 복잡도 : O(n^2)

최악 성능 시간 복잡도 : O(n^2)

최선 성능 시간 복잡도 : O(n^2)

 

▶소스코드

void SelectionSort(int arr[], int size)
{
    int min, temp;
    for (int i = 0; i < size - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        if (i != min)
        {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

위 소스는 오름차순 정렬이다.

 

▶해석

비교하는 값은 배열 길이 마지막까지 반복할 필요가 없으므로 size-1까지 반복한다.

for (int i = 0; i < size - 1; i++)

 

min변수는 가장 작은 배열 값의 자릿수를 저장하는 변수로 언제든지 바뀔 수 있다.

min = i;

 

i값이 저장된 min의 배열 값과 비교하기 위해 자신을 제외한 다음 자릿수인 j=i+1부터 시작한다.

앞에서부터 차근차근 정렬되므로 굳이 j=0부터 반복할 필요가 없다.

for (int j = i + 1; j < size; j++)
{
    if (arr[j] < arr[min])
    {
        min = j;
    }
}

 

i==min이라면 가장 작은 값이 i이므로 치환할 필요가 없고, i!=min이라면 치환을 해준다.

if (i != min)
{
    temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
}

 

▶예시

#include <stdio.h>

void SelectionSort(int arr[], int size)
{
    int min, temp;
    for (int i = 0; i < size - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        if (i != min)
        {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

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

    SelectionSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

결과

0 1 2 3 4 5 6 7 8 9