[ 자료구조 ] 정렬 - 02 . 버블 정렬

[ 버블 정렬 ]

[ 버블 정렬 ]

알고리즘이 데이터를 정렬하는 과정이 물 속 깊은 곳에서 일어난 거품이 수면을 향해

올라오는 모습과 같아 붙여진 이름이다 .

 

버블 정렬은 데이터 집합을 순회하면서 집합내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다 .

 

[ 버블 정렬의 과정 ]

1. 교환전 요소 둘 사이를 비교, 이웃끼리 올바른 위치에 있는지 확인한다 . (오름차순이라면 왼쪽은 오른쪽 보다 작다)
2. 올바르지 않다면 두 요소의 위치를 바꾸어 준다 .
3. 첫번째 , 두번째 요소간의 비교가 끝났다면 두번째 , 세번째 요소간의 비교를 수행한다 .
4. 해당 과정의 반복으로 마지막 요소는 올바른 위치에 있게 된다 .
5. 마지막 요소를 제외한 나머지 집합에서 다시 버블 정렬을 수행한다 .
6. 위 과정의 반복으로 정렬이 완료된다 .

 

[ 버블 정렬은 얼마나 빠를까 ]

[ 버블 정렬 ]

1시간내 30000명의 성적을 정렬한다면 ? (초당 200회 연산이 가능한 컴퓨터에서)

1시간에 720,000회 이내 작업을 마무리 할 알고리즘이 필요하다 .

그렇다면 버블 정렬은 ?

 

=>버블 정렬의 비교횟수는 = (n-1) + (n-2) +(n-3) .. (n-(n-1))이다 .

이는 (n-1) + (n-(n-1)) = n * (n-1)/2로 결국 , 버블 정렬의 비교 횟수는  n(n-1) / 2 가 된다 .

 

위의 식에 기반하여 30,000이라면 4억 5천만의 비교연산이 필요하므로 1시간내 작업을 완료 할 수 없다 .

 

[ 결론 ]

버블 정렬은 구현이 간단해 버그를 만들 가능성이 적지만 실제 상용 프로그램에 쓰기에는 문제가 있다 .

그럼에도 불구하고 이를 배움은 왜 버블정렬이 비효율적인지 깨닫고 , 효율적인 알고리즘에 대한 갈증을

느끼는게 필요하기 때문이다.

 

=>버블 정렬은 미리 정렬이 되어 있더라도 모든 루프를 돌며 비교를 수행하는 미련한 알고리즘이다 .

 

[ 버블 정렬 구현]

[ BubbleSort.cpp ]

#include<stdio.h>

void BubbleSort(int DataSet[], int Length)
{
	int i = 0, j = 0, temp = 0;

	for (i = 0; i < Length - 1; i++)
	{
		for (int j = 0; j < Length - (i + 1); j++)
		{
			if (DataSet[j] > DataSet[j + 1])
			{
				temp = DataSet[j + 1];
				DataSet[j + 1] = DataSet[j];
				DataSet[j] = temp;
			}
		}
	}
}

int main(void)
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	BubbleSort(DataSet, Length);

	for (i = 0; i < Length; i++)
	{
		printf("%d\t", DataSet[i]);
	}
	return 0;
}