Bubble Sort

버블 정렬

버블 정렬은 옆에 있는 값과 비교하여 더 작은 값을 앞으로 보내는 것이다.

 

따라서

 5 3 4 1 2 라고 있으면

3 5 4 1 2

3 4 5 1 2

3 4 1 5 2

3 4 1 2 5

이와 같이 한번 순회를 하면 맨 뒤가 제일 큰 값이 오게 된다.

한번 순회가 완료되면 맨 뒤는 비교해 줄 필요가 없다.

따라서 이중 for문을 이용하여 다음과 같이 구현 할 수 있다.

 

vector<int> BubbleSort(vector<int>& _vec)
{
	for (int i = 0; i < _vec.size(); ++i)
	{
		for (int j = 0; j < _vec.size() -1 - i; ++j)
		{
			if (_vec[j] > _vec[j + 1]) // 앞의 값이 더 크다면
			{
				int iTemp = _vec[j];
				_vec[j] = _vec[j + 1];
				_vec[j + 1] = iTemp;
			}
		}
	}
	return _vec;
}

연산은 등차수열의 합의 개수만큼 연산을 하기 때문에

N(N+1) / 2 만큼 연산을 하고

따라서 시간복잡도는 O(N^2) 를 가지게 된다.

또한 옆과 비교에서 계속해서 자리를 바꾸는 연산을 하기 때문에 정렬 중에 매우 느린편에 속한다.