[Sorting 04] Bubble Sort의 개념 및 구현

들어가며

---

이제 주요 정렬(sort) 알고리즘의 반정도 포스팅을 했다.
어떻게 이렇게 다양한 정렬 알고리즘들을 생각해냈는지 그저 신기할 따름이다.

그간 알고리즘들이 머릿 속에서 정리가 안된 채 널부러져 있는 느낌이었는데
블로그 포스팅을 하면서 점점 정리가 되는 기분이 들어서 좋다.
오늘은 쉬운 정렬 알고리즘 중에 하나인 'Bubble Sort'에 대해 알아보자.

개념 및 특징

---

1. 비교횟수: O(N²)
2. 자리 교환 횟수
   • 최선의 경우
     - 이미 정렬이 된 경우
     - 한번도 바꾸지 않아도 된다.
     - O(1)
   • 최악의 경우
     - 꺼꾸로 정렬이 된 경우
     - O(N²)

알고리즘

---

1. 인접한 두 수를 비교하여 큰 수를 뒤로 보낸다.
2. 한번 순회할 때마다 비교하는 수가 하나씩 줄이면서, 정렬이 완료될 때까지 1의 과정을 반복한다.

소스코드(C++)

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

typedef vector<int>::iterator IT; 

void bubbleSort(IT bit, IT eit)
{
	int len = eit - bit;
	for(int i=0;i<len;++i) {
		for(IT it=bit;it!=eit-i;++it) {
			if(it+1 < eit-i && *(it+1) < *it) {
				int tmp = *it;
				*it = *(it+1);
				*(it+1) = tmp;
			}
		}
	}
}

int main(void)
{
	int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	vector<int> vc(a, a+sizeof(a)/sizeof(a[0]));
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	bubbleSort(vc.begin(), vc.end());
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
		
	return 0;
}

관련 문제

---

사실 정렬과 관련된 문제라면 어떤 문제든 풀어도 좋지만, 시간 복잡도가 너무 커서 백준에 있는 문제들은 bubble sort로 풀면 시간초과가 뜰 것이므로, 관련 문제는 다루지 않는다.