얌생

버블 정렬이란, 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면

자리를 바꾸는 정렬 알고리즘을 말한다.

이름의 유래는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

버블 정렬 알고리즘의 구체적인 방법

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두번째 자료와 세 번째 자료를 .. 이런 식으로 ( 마지막 - 1 )번째 자료와 마지막 자료를 비교해 교환하면서 자료를 정렬한다.

void BubbleSort(int list[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			// 현재 위치와 앞 위치 데이터 비교
			// 현재 위치 데이터가 더 크면 스왑
			if (list[j] > list[j + 1])
			{
				swap(list[j], list[j + 1]);
			}
		}
	}
}

시간복잡도

시간복잡도를 계산하면, ( n - 1 ) + ( n - 2 ) + ( n -3 ) + .... + 2 + 1 => n(n-1)/2 이므로, O(n^2)다.

또한, Bubble Sort는 정렬이 되어있던 안되어있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두

시간 복잡도가 O(n^2)로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 구현이 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. ( 제자리 정렬 )
• 안정 정렬(Stable Sort)이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 되어있지 않은 원소가 정렬 되었을때의 자리로 가기 위해, 교환 연산(swap)이 많이 일어나게 된다.