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

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

---

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자!

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

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자!!!

//1

1 10 5 8 7 6 3 4 2 9

1 5 10 8 7 6 3 4 2 9

1 5 8 10 7 6 3 4 2 9

1 5 8 7 10 6 3 4 2 9

⁞

1 5 8 7 6 3 4 2 9 10

//2

1 5 8 7 6 3 4 2 9 10

1 5 7 8 6 3 4 2 9 10

1 5 7 6 8 3 4 2 9 10

⁞

1 5 7 6 3 4 2 8 9 10

⁞

1 2 3 4 5 6 7 8 9 10

소스코드 구현 (C++)

int main()
{
	int temp;
	int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 };
	//버블 정렬	
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 9 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

	//출력
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ", ";
	}
	return 0;
}

출력 결과

시간 복잡도 계산

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

10 + 9 + 8 + 7 +...+ 1 //등차수열

= 10 * (10 + 1) / 2 = 55 

= N * (N + 1) / 2

시간 복잡도로 표현한다면

= O(N * N)

---

버블정렬의 시간복잡도는 O(N^2)으로 선택정렬과 같다. 하지만 시간을 측정해보면 버블정렬이 더 시간이 오래걸리는것을 발견할 수 있는데 같은 등차수열이지만 버블정렬은 계속 스왑을 하는 계산을 하기때문에 시간이 더 소요하게 된다.

가장 느린 정렬이라고도 할수 있다!