거품 정렬(Bubble Sort)

개념 요약

• 서로 인접한 두 원소의 대소 비교하여 정렬하는 알고리즘
• 시간 복잡도가 $O(n^2)$로 느리다.
• 코드가 단순하다.

 

---

정렬 과정

1. 1번째 회전에 i번째 원소와 i+1번째 원소의 대소를 비교하여 조건에 맞지 않는다면 swap 한다.(i는 1부터 마지막-1이다.)
2. 1회전을 수행하면 가장 큰 원소가 맨뒤로 이동하여 2회전으로는 마지막 원소는 정렬에 제외되는데,
   이처럼 회전 한 번당 정렬된 원소가 하나씩 뒤에 쌓이는 것이다.

 

---

코드(c++)

void	bubblesort(std::vector<int> &unsorted_array)
{
	int	temp = 0, max = unsorted_array.size();
	// 마지막 원소에서 제외할 원소들
	for (int i = 0; i < max; ++i)
	{
    	// 비교하는 원소들
		for (int j = 1; j < max - i; ++j)
		{
			// 조건확인(오름차순)
			if (unsorted_array[j - 1] > unsorted_array[j])
			{
				// swap
				temp = unsorted_array[j - 1];
				unsorted_array[j - 1] = unsorted_array[j];
				unsorted_array[j] = temp;
			}
		}
	}
}

 

---

시간 복잡도

• 수식은 아래와 같이 볼 수 있다.
  $$(n - 1) + (n - 2) + (n - 3) + (n - 4)... => \frac {n(n + 1)}{2}$$
• 정렬의 여부를 확인하지 않고 비교하기 때문에 최선, 평균, 최악의 경우 모두 $O(n^2)$이다.

 

---

공간 복잡도

• 주어진 배열 내에서 교환으로 정렬이 수행되므로 $O(n^2)$이다.

 

---

장단점

• 구현이 간단하고 직관적이다.
• 시간 복잡도가 $O(n^2)$으로 많이 비효율적이다.