이번에는 반복 알고리즘일 이용하는 선택 정렬 알고리즘을 알아봅시다.
선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.
선택 정렬 알고리즘을 의사코드(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;
}