알고리즘- 정렬(Bubble Sort)

버블 정렬이란

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

배열에 6,5,2,8이 저장되어 있다고 했을 때 한 번의 반복문을 실행했을 때의 결과물은

배열의 가장 오른쪽은 배열안에 가장 큰 수가 확정적으로 위치한다.

 

장점

구현이 매우 간단하다.

단점

시간복잡도가 최악

최악, 최선, 평균 모두 O(n ^ 2)의 시간 복잡도를 가진다.

 

버블 소트는 단점이 명확하다.

따라서 사용처를 찾는것이 쉽지는 않다.

하지만 알아야 하는이유는

게임에서 알고리즘은 한 개만 사용하는 것이 아닌 여러 개를 혼합해서 사용할 때가 있다.

따라서 쉬운 만큼 이런 것도 있구나 하고 넘어가자.

사라리 게임을 구현하는 데 사용하기도 한다.

 

시간 복잡도

최선	최악	평균
O(n ^2) 최선,최악,평균 모두 동일하게 일정하다.

 

구현 내용

void BubbleSort(std::vector<int>& mArray)
{
	printf("정렬 시작\n");
	int Size = mArray.size() - 1;
	for(int i = 0; i < mArray.size(); i++)
	{
		//반복문이 돌아가면서 가장 오른쪽은 확정
		//따라서 반복횟수를 1씩 감소
		for(int j = 0; j < Size;j++)
		{
			if(mArray[j] > mArray[j + 1])
			{
				int temp = mArray[j];
				mArray[j] = mArray[j + 1];
				mArray[j + 1] = temp;
			}
		}
		Size--;
	}

	
	printf("결과 값 출력\n");
	for(auto K : mArray)
	{
		printf("[%d]", K);
	}
}

실행 결과