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

1. 유튜브 동영상 강의

1.1 선택 정렬 알고리즘

선택 정렬 알고리즘 동영상 강의

1.2 선택 정렬 알고리즘 구현

선택 정렬 알고리즘 구현 동영상 강의

2. 알고리즘

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

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

선택 정렬 알고리즘을 의사코드(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

선택 정렬 실행 화면

3. 점근식 계산

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

선택 정렬의 내부 반복문의 수행 시간을 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)이라는 차이가 있어요. 물론 전체 성능에 미치는 영향은 아주 작아요.

 

4. 소스 코드

//선택 정렬(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 <stdio.h>
#include <stdlib.h>
#include <conio.h>

#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;
}