[Algorith] 버블 정렬 (Bubble Sort)

정렬 전 3  7  9  1  2

1차 정렬 3  7  1  9  2   ->  3  7  1  2  9     1차 정렬 끝

2차 정렬 3  1  7  2  9   ->  3  1  2  7  9     2차 정렬 끝

3차 정렬 1  3  2  7  9   ->  1  2  3  7  9     3차 정렬 끝 

정렬이 한번 끝날 때 마다 끝에 가장 큰 수가 정렬된다.

비교 횟수는 N^2/2가 된다.
만약 최악의 경우일 경우 비교와 이동 횟구 모두 N^2/2가 된다.

Big-O 표기법의 의한 O(N^2)이 된다.

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

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

// 함수의 프로토타입

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

int Buf[MAX];


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

	printf("정렬 후 데이터\n");
	BubbleSort();
	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 BubbleSort(void) // 정렬 함수
{
	int i, j, dummy;

	for(i=MAX -1; i>=0; i--)
	for(j=1; j<=i; j++)
	{
		if(Buf[j-1] > Buf[j])
		{
			dummy = Buf[j-1];
			Buf[j-1]= Buf[j];
			Buf[j]=dummy;
		}
	}
}

void DisplayBuffer(void)
{
	int i;

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