[Algorith] 선택 정렬 (Selection sort)

정렬 전      3   7   9   1   2   
1차 정렬     1   7   9   3   2
2차 정렬     1   2   9   3   7
3차 정렬     1   2   3   9   7
4차 정렬     1   2   3   7   9

정렬을 할때 위와 같이
첫 번째 원소의 값을 그 뒤의 나머지 원소들 중 가장 작은 값과 바꾼다.
두번째 원소의 값을 그 뒤의 원소들 가장 작은 값과 바꾼다.
위와 같이 반복하면 정렬이 끝난다.

선택 정렬은 비교 하는데 N^2/2회나 되지만 데이터 교환에는 N번의 횟수면 된다.
때문에 정렬 데이터가 큰 경우 다른 정렬 알고리즘에 비해 유용하다.

Big-O 표기법의 의한 계산 O(N^2)
(단순 계산으로는 for문이 중첩되는 경우므로 N*N=N^2이 나온다.)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

// 함수의 프로토타입

void MakeRandomNumber(void);
void SelectionSort(void);
void DisplayBuffer(void);
int IsNumberExit(int, int);

int Buf[MAX];

void main()
{
	printf("정렬할 데이터의 초기화\n");
	MakeRandomNumber();
	DisplayBuffer();

	printf("정렬 후 데이터\n");
	SelectionSort();
	DisplayBuffer();
	printf("\n");
}

//정렬할 데이터의 초기화
void MakeRandomNumber(void)
{
	int i, Num;
	i=1;
	Buf[0]=100;
	while(i < MAX)
	{
		Num = rand() % MAX;

		if(!IsNumberExit(Num, i))
		{
			Buf[i]=Num;
			i++;
		}
	}
}

// 이미 생성된 값이 아닌지를 검사
int IsNumberExit(int number, int index)
{
	int i;

	for(i=1; i < index; i++)
	{
		if(Buf[i] == number)
		return TRUE;
	}
	return FALSE;
}

void SelectionSort(void) // 정렬 함수
{
	int i, j, min, dummy;

	for(i=0; i < MAX; i++)
	{
		min=i; // i의 값을 하나씩 올려 정렬된 값 뒤로 계산하게 하는 역할
		for(j=i+1; j < MAX; j++)
		if(Buf[j] < Buf[min])
		min = j; // 최소값을 바꾼다.
		dummy = Buf[min]; // 서로 자리를 바꾼다.
		Buf[min] = Buf[i];
		Buf[i]=dummy;
	}
}

void DisplayBuffer(void)
{
	int i;

	for(i=0; i < MAX; i++)
	{
		printf("%4d", Buf[i]);
		if((i % 10) == 9 )
		printf("\n");
	}
	printf("\n");
}