본문 바로가기

Programming/Algorithm

[정렬 알고리즘] 버블 소트(거품정렬)

반응형

버블 소트는 정렬 알고리즘의 한 종류입니다.

정렬 알고리즘은 무작위로 있는 정보를 순차적으로 재배치 시키는 것이 목적입니다.

버블 소트는 각종 정렬 알고리즘 중에서도 기본으로 여겨지는 알고리즘입니다.

정렬 알고리즘은 퀵 정렬, 삽입 정렬, 힙 정렬, 선택 정렬 등 여러가지 방법이 존재합니다.

보통은 속도가 빠른 퀵소트를 많이 사용합니다.

퀵소트를 구현하는데는 재귀 함수 방식이 많이 활용됩니다.

재귀 함수에 대한 설명은 아래 링크에서 확인 가능합니다.

2014/12/04 - [Programming/C&C++] - 재귀 함수 & 재귀적 함수호출(recursive function call)

그럼 본격적으로 버블 소트에 대해서 알아보도록 하겠습니다.

만약 버블 소트의 코드만 필요하다만 가장 하단의 코드를 참조하시면 됩니다.

버블 소트의 코드를 확인해 보도록 하겠습니다.

#include <iostream>
using namespace std;

template <class T>
void MySwap(T& a, T &b)
{
	T tmpVal = a;
	a = b;
	b = tmpVal;
}

template <class T>
void BubbleSort(T* arVal, int nCount)
{
	int i = 0, j = 0;
	
	for (i = nCount - 2 ; i >= 0 ; --i)
	{
		for (j = 0 ; j <= i ; ++j)
		{
			if (arVal[j] > arVal[j + 1])
			{
				MySwap(arVal[j], arVal[j + 1]);
			}
		}
	}
}

int main()
{
	int arNoSort[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
	for (int i = 0; i < sizeof(arNoSort) / sizeof(int) ; ++i)
	{
		cout << arNoSort[i] << " ";
	}
	cout << endl;

	BubbleSort(arNoSort, sizeof(arNoSort) / sizeof(int));

	for (int i = 0; i < sizeof(arNoSort) / sizeof(int); ++i)
	{
		cout << arNoSort[i] << " ";
	}
	cout << endl;

	return 0;
}

C++의 템플릿(template)을 사용하여 다양한 타입에 대응할 수 있도록 작성하였습니다.

템플릿은 C++을 강력하게 만드는 문법입니다.

버블 소트의 기본 개념은 버블이 움직인다는 점입니다.

다음과 같은 배열이 있을 때 버블 소트가 동작하는 과정을 보도록 하겠습니다.

버블은 처음에 다음과 같이 4와 2를 먼저 비교하게 됩니다.

4가 2보다 크기 때문에 MySwap을 사용하여 위치를 변경해 줍니다.

현재 위치가 정상적으로 위치가 변경되었기 때문에 버블을 다음 위치로 이동시킵니다.

이번에도 위치를 변경한 이후에 다시 다음 위치로 이동해야 합니다.

다시 위치를 바꿔야 하기 때문에 바꾼 다음에 이번에는 끝까지 가는 걸 보도록 하겠습니다.

한 바퀴를 완전히 돌고나서 7(가장 큰 값)이 정렬되었습니다.

이미 7은 정렬이 된 상태이기 때문에 이제 더 이상은 맨 끝까지 갈 필요가 없습니다.

다음으로 남은 숫자들을 정렬해보도록 하겠습니다.

이런 식으로 계속 정렬이 진행되는 것입니다.

버블 정렬의 함수에는 첫 번째 for 문과 그 안에 두 번째 for문이 존재합니다.

첫 번째 for (i = nCount - 2 ; i >= 0 ; --i) 는 거품이 움직여야 할 범위입니다.

처음에는 7개 숫자가 모두 정렬이 안되어 있기 때문에 6 번째 숫자까지 이동해야 합니다.

정렬이 진행될 수록 가야할 위치가 짧아지기 때문에 계속 --i를 해주는 것입니다.

그 다음 for문인 for (j = 0 ; j <= i ; ++j)는 실제 버블이 움직이는 부분입니다.

버블은 i위치까지 가기 위해서 항상 0부터 시작을 합니다.

버블 정렬은 비교적 구현이 간편한 정렬입니다.

여기서 성능을 향상시킬 수 있는 방법이 존재합니다.

현재 2바퀴만에 모든 정렬이 완료되었습니다.

그렇지만 버블 정렬은 꿋꿋이 계속 정렬을 수행하게 됩니다.

정렬이 끝났다는 flag를 추가해서 정렬이 끝나면 불필요한 정렬을 막을 수 있습니다.

소스 코드는 다음과 같은데 위의 정렬과 차이점을 스스로 비교해 보시기 바랍니다.

template <class T>
void MySwap(T& a, T &b)
{
	T tmpVal = a;
	a = b;
	b = tmpVal;
}

template <class T>
void BubbleSort(T* arVal, int nCount)
{
	int i = 0, j = 0;
	bool bFlag = true; // <--
	for (i = nCount - 2 ; i >= 0 && bFlag ; --i) // <--
	{
		bFlag = false; // <--
		for (j = 0 ; j <= i ; ++j)
		{
			if (arVal[j] > arVal[j + 1])
			{
				bFlag = true; // <--
				MySwap(arVal[j], arVal[j + 1]);
			}
		}
	}
}

버블 소트와 버블 소트의 성능을 개선하는 방법에 대한 설명을 마칩니다.

반응형