알고리즘 < 버블 정렬(Bubble Sort)>

버블 정렬 개요

 

버블정렬은 정렬알고리즘 중에서 비교적 쉬운 정렬 알고리즘으로 구현이 쉽고 간편하게 사용할 수 있지만 성능면에서는

다소 아쉬운 알고리즘입니다. 

 

이번 포스팅에서는 버블정렬이 무엇인지 그 원리를 이해하고 직접 코드로 구현해보는 과정까지 작성해보겠습니다.

 

버블정렬의 원리

 

 

배열에 왼쪽부터 차례대로 3, 2, 4, 1 이란 정수가 담겨있다고 가정합니다. 

 

이를 오름차순으로 정렬하면 1, 2, 3, 4 가 될 것입니다. 

 

버블 정렬은 쉽게 말해 현재 값과 다음 값을 비교하며 정렬하는 방식이라 볼 수 있습니다.

 

 

Current 는 현재 인덱스이며 Next 는 현재 인덱스의 바로 다음 인덱스입니다.

 

오름차순으로 정렬할 것이므로 두 값을 비교하여 더 작은 값을 앞에 배치해야합니다. 

 

위의 예시대로라면 두 값을 서로 바꿔주어야 합니다.

 

 

바꾸는 동시에 인덱스는 하나씩 증가시켜줍니다. 

 

그리고 다시 두 값을 비교합니다. 3과 4는 잘 정렬되어있기에 바꾸지 않습니다.

 

인덱스를 증가시키면 다음과 같습니다.

 

 

값을 바꿔 주어야하겠네요. 

 

 

이렇게 한 사이클을 돌게되면 정렬의 우선순위가 가장 낮은 요소를 맨 뒤로 보내게됩니다.

 

그리고 정렬이 완료된 데이터를 제외하고 이를 반복합니다. 

 

버블정렬을 코드로 구현해보기

 

void BubbleSort(int arr[], int n)
{
	int i, j; // 각각 현재 인덱스, 다음 인덱스 변수
	for (i = 0; i < n - 1; i++) 
	{
        // 현재 인덱스의 다음 인덱스 부터 정렬 된 데이터를 제외하고 반복
		for (j = i + 1; j < n - i ; j++) 
		{
			if (arr[i] < arr[j]) // 정렬 기준
			{
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
}

 

성능 평가하기

 

정렬 알고리즘의 성능은 '비교연산'과 데이터 이동을 위한 '대입연산' 의 횟수로 판단합니다. 

 

우선 비교연산에 의한 빅오 부터 계산해봅시다.

 

전체 데이터가 n 개일 때 최악의 경우에서 비교 연산이 몇 번 수행되는지 계산하면 됩니다.

 

버블 정렬은 처음 n - 1 개 만큼 비교한 뒤 그 뒤로는 하나씩 비교연산 횟수가 줄어듭니다. 

 

따라서 첫 째항이 n - 1 이고 공차가 1 인 등차수열의 합 공식을 생각하면 됩니다. 

 

이를 빅오로 표기하면 n의 제곱이 되겠네요.