2) 버블 정렬(Bubble Sort)

---

문제는 저번에 했던 것과 동일하다.

<다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.>

(1, 10, 8, 3, 5, 4, 7, 9, 2, 6)

버블 정렬도 선택 정렬과 같이 매우 직관적이다.
바로 가까이에 있는 두 숫자를 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복한다.
구현은 쉽지만 가장 비효율적인 알고리즘이다.

#include <iostream>
using namespace std;

int main() {
	int temp;
	int array[10] = { 1, 10, 8, 3, 5, 4, 7, 9, 2, 6 };
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 9-i; j++)
		{
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}
}

---

계속 반복해서 두 숫자중 작은것을 앞으로 보낸다.
버블 정렬의 시간 복잡도는 선택 정렬과 동일한 O(N^2)이다.
하지만 선택 정렬보다 더 비효율적인 이유는 양옆으로 (탐색 -> 비교 -> 바꿈) 이 작업을 반복 수행하기 때문에 수행되는 연산이 더 많다.
그래서 실제 수행시간은 선택 정렬 < 버블 정렬 이다.