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

 원리 

1. 첫 인덱스부터 인접한 두 원소를 "비교"하자

2. 가장 큰 원소를 "맨뒤"로 보내자

 

[ 1, 55, 30, 20, 47 ]

 

(1, 55), 30, 20, 47 --> (1, 55), 30, 20, 47  

1, (55, 30), 20, 47 --> 1, (30, 55), 20, 47

1, 30, (55, 20), 47 --> 1, 30, (20, 55), 47

1, 30, 20, (55, 47) --> 1, 30, 20, (47, 55)

 

 

이 과정을 거쳐서 55이라는 숫자가 맨뒤로 정렬 된 것을 확인할 수 있습니다.

이 과정을 총 n번 반복하면 됩니다.

 

 구현 

vector<int> vec = { 55, 7, 78, 12, 42, 3, 2 };

	for(int i = 0; i < vec.size(); ++i)
		for(int j = 0; j < vec.size()-1; ++j)
			if (vec[j] > vec[j + 1])
			{
				vec[j] ^= vec[j + 1];
				vec[j + 1] ^= vec[j];
				vec[j] ^= vec[j + 1];
			}

다음과 같이 "인접한 원소"들을 비교하며 "가장 큰 원소"를 맨뒤로 보내는 과정을 반복하고 있습니다.

 

위는 오름차순으로 정렬한 것이고, 내림차순을 위해서는 반대로 "인접한 원소"들을 비교하며 "가장 작은 원소"를 맨뒤로 보내는 과정을 반복하면 됩니다.

 

버블 정렬은 정렬 중 시간복잡도가 높은 축에 속하는데, 간단하게 사용할 때 구현할 수 있습니다. 또한 몇가지 추가하면 커팅이 가능하게 됩니다.

 

vector<int> vec = { 55, 7, 78, 12, 42, 3, 2 };

	for (int i = 0; i < vec.size(); ++i)
	{
		bool flag = true;
		for (int j = 0; j < vec.size() - 1; ++j)
			if (vec[j] > vec[j + 1])
			{
				vec[j] ^= vec[j + 1];
				vec[j + 1] ^= vec[j];
				vec[j] ^= vec[j + 1];
				flag = false;
			}
		if (flag) break;
	}

 

다음과 같이 flag 변수를 주어서 "인접한 원소들간의 비교"가 변함이 없을 때는 모든 수가 정렬이 된 것이므로 바깥 for문을 탈출 할 수 있습니다. 하지만, 원소들간의 정보를 이용하지 않고 있는데, 시간 복잡도를 줄이기 위해 불필요한 과정을 줄이는 정렬이 필요해 보입니다.

 

 시간복잡도 

 

그렇다면 서로 인접한 원소들을 n-1만큼 순회하면서 비교하고 총 n번 반복하기 때문에 O(n^2)의 시간복잡도를 가지게 됩니다.

 

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	사진 참고

버블 정렬 런타임 (랜덤 정수 60,000개)

정수 60,000개로 비교 결과 50s ~ 52s 사이의 결과가 나왔습니다. 고작 6만개의 정수 비교인데.. 버블정렬은 거를게요ㅎㅎ

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

 참조 

위키백과 - 버블 정렬

거품 정렬 - 위키백과, 우리 모두의 백과사전