버블 정렬(Bubble Sort)

버블 정렬

버블 정렬(Bubble Sort)은 서로 인접한 두 원소를 비교해서 교환하는 알고리즘으로, 원소가 이동하는 모습이 거품이 수면으로 올라오는 듯한 모습과 비슷하기 때문에 지어진 이름이라고 합니다. 

처음에는 첫 번째 원소와 두 번째 원소를 비교하고 다음에는 두 번째 원소와 세 번째 원소, 세 번째 원소와 네 번째 원소 이런 식으로 마지막에는 끝에서 두 번째 원소와 첫 번째 원소를 비교하고 교환합니다.

이 과정을 계속해서 반복하는데 한 번 이 과정을 반복하면 가장 큰 원소가 마지막으로 이동하므로 맨 끝에 있는 원소는 정렬 과정에서 제외됩니다.

정렬해야 할 원소의 개수 - 1만큼 위 과정을 반복하면 정렬이 완료됩니다.

 

버블 정렬 예시

 

버블 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

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

	for (int i = 0; i < number - 1; i++)
	{
		for (int j = 0; j < number - 1 - i; j++)
		{
			if (numbers[j] > numbers[j + 1])
			{
				Swap(&numbers[j], &numbers[j + 1]);
			}
		}
	}

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

정렬하려는 배열이 이미 정렬되어 있는 경우 반복문을 빠져나오도록 해서 알고리즘을 최적화시킬 수 있습니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];
	bool is_swapped;

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

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

	for (int i = 0; i < number - 1; i++)
	{
		is_swapped = false;

		for (int j = 0; j < number - 1 - i; j++)
		{
			if (numbers[j] > numbers[j + 1])
			{
				Swap(&numbers[j], &numbers[j + 1]);
				is_swapped = true;
			}
		}

		if (is_swapped == false)
			break;
	}

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

버블 정렬 시간복잡도

최선	평균	최악
n2	n2	n2