C++ / Algorithm 버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)란 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬 방식입니다. 거품 정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심입니다. 

 

정렬 프로세스 

1. 인접한 두 수의 대소를 비교한다.

2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다.

3. 나머지 요소들도 동일한 매커니즘으로 정렬한다. 

 

구현이 쉬워서 자주 사용된다. 하지만 조건이 맞는 상황이 주어질 때 매번 정렬하기 때문에 실행 속도를 느리게 할 수 있다는 단점이 있습니다.

무작위 배열 수의 버블 정렬 예시

예시

다섯 개의 숫자를 정렬한다고 예시를 들겠습니다. 

i 가 0 일 때 이중 for문에서 n-1번 비교, 

i 가 1일 때 이중 for문에서 n-2번 비교,

...

 

i 가 3일 때 이중 for문에서 n-4 = 1번 비교를 합니다. 

오름차순 정렬이기 때문에 j의 2중 for문 한번 돌 때 마다 숫자들 중 최댓값이 가장 오른쪽에 배치됩니다.

이 때문에 j의 이중 for문의  조건식이 j < n - i - 1 로 잡습니다.

 

시간 복잡도

 

위에서 설명한 것과 같이

(n-1) + (n-2) + ... + 1 = n(n-1) / 2 = O(n^2) 를 갖습니다. 

입력 배열의 정렬 여부에 상관없이 일정한 시간 복잡도를 보장합니다.

 

int main()
{
	int n, tmp, idx, a[101];

	scanf("%d", &n);

	for(int i = 0; i < n ; i ++)
	{
		scanf("%d", &a[i]);
	}

	for(int i = 0; i < n-1; i++)
	{
		// j로 한번 순회할 때 마다 오름차순의 경우 가장 큰 원소를 오른쪽으로 정렬합니다.
		// i 가 증가해, 2중 for문 j의 조건식에 따라 전부 순회하지 않습니다.
		for(int j = 0; j < n -i - 1; j++)
		{
			// 오름차순 정렬
			if(a[j] > a[j+1])
			{
				tmp = a[j];
				a[j] = a[j+1];
				a[j +1] = tmp;
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		printf_s("%d ", a[i]);
	}
	

    return 0;
}

위 2줄은 입력 / 세 번째 줄이 버블 정렬 결과 출력