[알고리즘] 버블 정렬(bubble sort)

 버블 정렬은 가장 기초적인 소팅 형식으로, 단순하게 구현이 가능하기 때문에 소팅의 개념을 이해하기 위한 교육용으로 적합합니다.

 위 처럼 정렬되는 모습이 마치 거품이 일어나는 것과 유사하다고 하여 버블 정렬이라고 합니다.

 

어떤 원리로 동작하나요 ?

 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.

 

 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

이 순서는 코드의 조건을 구성하는 방식에 따라 오름차순과 내림차순 두 가지 형태로 출력됩니다.

 

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

 

 1회전을 수행하고 나면 가장 큰 자료가 가장 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

 

#include <stdio.h>

int main(void)
{
	int i, j, temp;
	int array[10] = { 5, 10, 2, 3, 7, 1, 9, 4, 6, 8 };

	for (i = 0; i < 10; i++)
	{
		// 1회전 이후 1개 배열 제외시키기
		for (j = 0; j < 9 - i; j++)
		{
			// n 번째 원소값 > n+1 번째 원소값 이면? = 오름차순 정렬 방식 선언
			if (array[j] > array[j + 1])
			{
				// temp 에 n 번째 원소값 저장,
				temp = array[j];
				// n 번째 원소값 위치에는 n+1 번째 원소값 저장,
				array[j] = array[j + 1];
				// n+1 번째 원소값 위치에는 temp 에 저장시킨 n 번째 원소값 저장
				array[j + 1] = temp;

				// 위 3가지 스왑을 통해 양쪽 원소의 위치가 서로 오름차순으로 정렬되는 알고리즘
			}
		}
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", array[i]);
	}

	return 0;
}

 위 소스코드는 오름차순 버블 정렬이며, 내림차순으로 코딩하는 경우에는

아래와 같이 if 문의 조건 선언에서 n+1 번째 원소 값이 n 번째 원소 값보다 더 큰 경우로 수정해주면 됩니다.

if (array[j] < array[j + 1]) // 내림차순 정렬 방식 선언

 

 

 

 만약 함수를 통해서 더 간편하게 사용하려는 경우, 아래와 같은 소스코드를 참조하시면 되겠습니다.

#include <stdio.h>

void swap(int* n1, int* n2);

int main(void)
{
	int i, j, temp, arr[10];

	for (i = 0; i < 10; i++)
	{
		scanf_s("%d", &arr[i]);
	}

	//오름차순
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 9 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(&arr[j], &arr[j + 1]);
			}
		}
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	// 내림차순
	for (i = 0; i < 10; i++)
	{
		for (j = 0; j < 9 - i; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				swap(&arr[j], &arr[j + 1]);
			}
		}
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

void swap(int* n1, int* n2)
{
	int temp;

	temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}

 

 마지막으로, 버블정렬은 실무에서는 다른 정렬 알고리즘에 비해 시간복잡도가 비효율적이기 때문에 단순성에도 불구하고 거의 사용되지 않습니다.

 

 때문에 버블소팅은 정렬 알고리즘에 대한 공부를 시작하기에 앞서, 기초적인 개념을 잡아가는 것에 중점을 두시면 되겠습니다.