버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

-서로 이웃한 데이터들을 비교하며 

가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식-

최악의 경우 시간복잡도는 O(n^2),

최선의 경우 시간복잡도는 O(n),

평균 시간복잡도는 O(n^2)이다.

(시간 복잡도의 개념을 알고 싶다면 위키보다는 이 블로그를 추천한다.)

평균이 O(n^2)인 느린 알고리즘이지만, 병렬 처리에 적합하며 코드가 간단하다. 

왜 느리냐 하면은, 모든 요소에 대해 비교하고, 해당 되는 요소에 교환을 하기 때문.

데이터들을 교환 시킬 때 거품이 수면 위로 올라오는 것 같다 하여

버블 정렬이라고 한다.

(실제로 버블정렬 애니메이션을 보면 그렇게 보이는 것 같다)

-Sample Source-

	#include <iostream>
	using namespace std;
	int main()
	{
	int Array[5] = { 22,50,32,7,41 }; //정렬되지 않은 배열
	int Count=0 , ChCount = 0; //비교횟수 & 교환 횟수 카운터
	for (int i = 0; i < 4; i++)
	{
	for (int j = 0; j < 4 - i; j++)
	{
	Count++; //비교횟수 증가
	if (Array[j] > Array[j + 1]) //만약 왼쪽이 오른쪽값보다 크다면 교환
	{
	int TempVal = Array[j + 1];
	Array[j + 1] = Array[j];
	Array[j] = TempVal;
	ChCount++; //교환 횟수 증가
	}
	}
	cout << i + 1 << ") ";
	for (int k = 0; k < 5; k++) //매 Pass 마다의 배열 상태 출력
	cout << Array[k]<<" ";
	cout << endl;
	}
	cout << "비교 횟수: " << Count <<" 교환 횟수: " << ChCount;
	}

view raw BubbleSort.cpp hosted with ❤ by GitHub