[C언어 소스] 선택 정렬 (Selection Sort) 알고리즘

이번에는 반복 알고리즘일 이용하는 선택 정렬 알고리즘을 알아봅시다.

선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.

선택 정렬 알고리즘을 의사코드(pseudo code: 논리적인 수행 흐름을 이해할 수 있게 작성한 코드)는 다음과 같습니다.

알고리즘

선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)

    반복(i:=n;  i>1  ; i:= i-1)

        반복(max=0,j:=1; j<i ; j:=j+1)

            조건(compare(base[max], base[j]) < 0)

                max := j

        temp: = base[i-1]

        base[i-1] = base[max]

        base[max] = temp

선택 정렬
선택 정렬

점근식 계산

이번에는 선택 정렬 알고리즘 성능을 분석합시다.

선택 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i+1에서 n까지 순차적으로 증가하므로 비교를 n-i번 수행함을 알 수 있어요. 따라서 S(i)= n-i죠.

외부 반복문은 i가 0에서 n까지 순차적으로 증가하면서 내부 반복문을 수행하고 교환 1회합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 이죠.

따라서 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 = n+1 + n + n-1 + …+1

따라서 T(n)= n(n+1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 선택 정렬도 순차 정렬과 거품 정렬처럼 O(n^2)이네요.

하지만 교환하는 시간은 O(n)이라는 차이가 있어요. 물론 전체 성능에 미치는 영향은 아주 작아요.

소스 코드

//선택 정렬(Selection Sort)
#include <stdio.h>

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

void SelectionSort(int *base, int n);
int main(void)
{
    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
    SelectionSort(arr, 10);
    return 0;
}
void ViewArr(int *arr, int n);
void SelectionSort(int *base, int n)
{
    int i, j;
    int maxi;
    ViewArr(base, n);//현재 상태 출력
    for (i = n; i>1; i--)//정렬할 범위를 축소해 나갑니다.
    {
        maxi = 0;
        for (j = 1; j<i; j++)
        {
            if (base[maxi]<base[j])//더 큰 원소를 만나면
            {
                maxi = j;
            }
        }
        SWAP(base[maxi], base[i - 1]);//교환
        ViewArr(base, n);//상태 출력
    }
}

void ViewArr(int *arr, int n)
{
    int i = 0;
    for (i = 0; i<n; i++)
    {
        printf("%2d ", arr[i]);
    }
    printf("\n");
}

//https://ehpub.co.kr
//[언제나 C언어] 선택 정렬(Selection Sort) [예제 Center]
#include 
#include 
#include 
#pragma warning(disable:4996)
#define LENGTH(arr)  (sizeof(arr)/sizeof(arr[0]))
#define SWAP(i, j) {int t; t=i; i=j; j=t;}
#include //Sleep
enum Color
{
	LACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY,
	LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE
};
void changecolor(int color)
{
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}

void View2(int *base, int n,int i, int j, int max,int r)
{
	int s = 0;
	for (s = 0; s < n; s++)
	{
		if (s < j)
		{
			if (s == max)
			{
				changecolor(YELLOW);
			}
			else
			{
				changecolor(WHITE);
			}
		}
		else if (s == j)
		{
			changecolor(GREEN);
		}
		else if (s < i)
		{
			changecolor(WHITE);
		}
		else if (s >= i)
		{
			changecolor(PURPLE);
		}		

		printf("%2d ", base[s]);
	}		
	changecolor(WHITE);
	if (r)
	{
		printf("SWAP %d %d", base[i - 1], base[max]);
	}
	printf("\n");
}
void SelectionSort2(int *base, int n)//선택 정렬(base:컬렉션, n : 원소 개수)
{
	int max, j;
	for (int i = n; i > 1; i--)	//반복(i: = n;  i > 1; i: = i - 1)	
	{
		for (max = 0, j = 1; j < i; j++)//반복(max = 0, j: = 1; j < i; j: = j + 1)		
		{
			if (base[max] < base[j])//조건(base[max]< base[j])
			{
				max = j;//max: = j
			}
			View2(base, n, i, j, max, 0);
			Sleep(1000);
		}
		SWAP(base[i - 1], base[max]);//교환(base[i-1],base[max])
		View2(base, n, i, j, max, 1);
	}
}
void View(int *base, int n, const char *msg)
{
	for (int i = 0; i < n; i++)
	{
		printf("%2d ", base[i]);
	}
	printf("%s\n", msg);
}
void SelectionSort(int *base, int n)//선택 정렬(base:컬렉션, n : 원소 개수)
{
	int max, j;
	for (int i = n; i > 1; i--)	//반복(i: = n;  i > 1; i: = i - 1)	
	{
		for (max = 0, j = 1; j < i; j++)//반복(max = 0, j: = 1; j < i; j: = j + 1)		
		{
			if (base[max] < base[j])//조건(base[max]< base[j])
			{
				max = j;//max: = j
			}
		}
		SWAP(base[i - 1], base[max]);//교환(base[i-1],base[max])
	}
}

int main()
{
	int arr[10] = { 9,4,3,0,5,8,7,6,2,1 };
	View(arr, LENGTH(arr),"before");
	getch();
	SelectionSort2(arr, LENGTH(arr));
	View(arr, LENGTH(arr),"after");
	system("pause");
	return 0;
}

C언어 소스