정렬 알고리즘 - 버블 정렬 알고리즘

이번에 알아볼 알고리즘은 선택 정렬과 마찬가지로 기본적인 정렬 알고리즘 중 하나인 버블 정렬 알고리즘이다.

버블 정렬은 바로 옆의 값이 더 작다면 그 값과 자리를 바꾸는 연산을 반복하면서,

결론적으로는 가장 큰 값이 배열의 맨 오른쪽에 위치하게 된다.

그리고 처음으로 돌아와 바로 옆의 값과 대소를 비교하는 연산을 또 반복하고,

이미 연산이 완료된 부분을 제외하고 가장 오른쪽으로 큰 값을 보낸다.

이 일련의 과정을 계속 반복하는 알고리즘이다.

 

1,10,5,8,7,6,4,3,2,9 -> 이 숫자들을 정렬해보자.

코드는 c++로 작성하였다.

 

#include <iostream>
using namespace std;

int main()
{
	int temp = 0;
	int arr[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (int i = 10; i > 0; i--)
	{
		for (int j = 0; j < i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}

먼저 swap 연산을 위한 temp 변수를 정의하고, 숫자들을 담은 arr 배열을 정의했다.

그리고 for문을 도는데 바깥쪽 for문은 i가 10부터 시작해서 1씩 감소하도록 했다.

안쪽에 위치한 for문은 j가 0부터 시작해서 i-1까지 증가하도록 했는데,

j가 증가하면서 바로 옆의 값과 대소를 비교하며 계속해서 swap 연산을 진행한다.

안쪽의 for문을 전부 돌고 나면 그때의 최댓값이 배열의 i-1번째의 위치에 들어가게 된다.

i가 1이 되었을 때 마지막에 남아있던 값이 배열의 0번째의 위치에 들어가게 되고 연산은 끝이 난다.

 

버블 정렬은 역시 이해하기 쉬운 편이고 코드도 짧은 편이다.

하지만 선택 정렬과 마찬가지로 버블 정렬은 비효율적인 알고리즘 중 하나이다.

바깥쪽의 for문이 도는 동안 안쪽의 for문을 돌며 모든 경우를 체크해 swap연산을 진행하기 때문에,

버블 정렬의 time complexity는 역시 O(n^2) time이라고 할 수 있겠다.

버블 정렬도 실제로 활용하기에는 좋지 않은 알고리즘이므로,

실전에서는 다른 알고리즘을 사용하는 편이 좋겠다.