정렬 알고리즘 - 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

 

버블 정렬(Bubble Sort)이란?

 

 - 첫 번째 노드를 시작으로 인접 노드와 비교하여 순서가 잘못되어 있다면 두 원소를 바꾼다.

   이 과정을 반복하여 정렬하는 알고리즘이다.

 

 - 구현은 매우 간단하지만, 빈번한 데이터의 교환으로 인해 잘 사용되지는 않는다.

 

 - N개의 데이터가 주어졌을 때의 O($N^2$)시간 복잡도를 가진다.

 

---

 

버블 정렬의 예시(오름차순)

 

 

데이터가 7, 1, 4, 6, 8 순서로 주어졌다고 가정하자.

1. 첫 번째 원소와 두 번째 원소를 비교하여 올바른 순서가 되도록 위치를 바꿔준다.

2. 두 번째 원소와 세 번째 원소를 비교하여 올바른 순서가 되도록 위치를 바꿔준다.

3. 세 번째 원소와 네 번째 원소를 비교하여 올바른 순서가 되도록 위치를 바꿔준다.

4. 네 번째 원소와 다섯 번째 원소를 비교하여 올바른 순서가 되도록 위치를 변경해준다. (해당 예제는 이미 올바른 순서이기 때문에 순서가 변경되지 않는다.)

첫 라운드가 끝난 결과 제일 끝 원소가 정해진다.

 

 - 정해진 원소를 제외하고 위 과정을 계속하여 반복해서 원소를 정렬한다.

 

 

---

 

버블 정렬 코드(C++)

 

#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int> &bubbleVec)
{
	int maxSize = bubbleVec.size();
	int tmp = 0;
	for (int i = maxSize -1; i >0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (bubbleVec[j] > bubbleVec[j + 1])
			{
				tmp = bubbleVec[j];
				bubbleVec[j] = bubbleVec[j + 1];
				bubbleVec[j + 1] = tmp;
			}
		}
	}
}


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> bubbleVec{ 7,1,4,6,8 };

	cout << "== 정렬 전 ==\n";

	for (auto n : bubbleVec)
		cout << n << endl;;

	bubbleSort(bubbleVec);
	
	cout << "== 정렬 후 ==\n";

	for (auto a : bubbleVec)
		cout << a << endl ;

	return 0;
}

 

 - 실행 결과