버블 정렬 (C/C++ 구현, 시간 복잡도)

1. 버블 정렬

 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 

 

출처 - 위키피디아(https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC)

나의 해석 : 현재 인덱스와 다음 인덱스를 비교해서 현재 인덱스가 크다면 한칸씩 교환해준다.

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

전체 인덱스를 n번 연산하여 정렬한다.

1. 0~n번 인덱스까지 서로 인접한 인덱스 비교한다.

1.1 첫번째 정렬에서 제일 큰 인덱스 n번째 인덱스로 이동

1.2 두번째 정렬에서 2번째 큰 인덱스 n-1번째 인덱스로 이동

2. 1번을 n번 반족

 

시간 복잡도

1번째에서 n-1번 비교

2번째에서 n-2번 비교

n번째에서 1번 비교

n* ( (n-1) + (n-2) + ....+ 1 )

O(n^2)

 

특징

구현이 쉽다

O(n^2)의 시간복잡도를 갖는다

교환 비용이 많이 들어 활용 안된다.

 

소스 코드

#include <iostream>

using namespace std;
int a[5] = { 5,4,3,2,1 };
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void bubble_sort(int list[])
{
	int j;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5 - i-1; j++)
		{
			if (list[j] > list[j + 1])
			{
				swap(list[j], list[j + 1]);
			}
		}
		for (int i = 0; i < 5; i++)
			cout << a[i] << " ";
		cout << endl;
	}
}
int main()
{
	bubble_sort(a);
	for (int i = 0; i < 5; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}