[알고리즘]버블정렬(Bubble Sort)

버블정렬(Bubble Sort)

기본적으로 가장 간단한 정렬이라 생각이 듭니다.

앞 뒤를 비교해서 우선순위를 정해 교체하는 알고리즘이죠.

버블정렬(Bubble Sort)의 시간복잡도는 O(n2)가 됩니다. 분기문을 두번 돌아야 하니까요.

{3, 2, 5, 4, 1} 을 버블정렬을 통해 정렬을 하면 다음과 같은 과정을 거치게 됩니다.

< [ 3, 2, 5, 4, 1] 정렬 >

녹색은 이미 정렬된 상태이므로 그대로 두고, 빨간색은 교체(스왑) 시켜줍니다.

그리고 주황색은 이미 정렬된 상태로 건드리지 않는다는 의미 입니다.

< C++ 코드 >

#include 
using namespace std;

void bubbleSort(int arr[], int n)
{
	bool swapped = true;
	int j= 0;
	int tmp = 0;
	while(swapped)
	{
		swapped = false;
		j++;
		for(int i = 0; i < n - j; i++)
		{
			// 이 조건을 변경하여 오름차순, 내림차순을 설정합니다.
			if(arr[i] < arr[i+1])
			{
				tmp = arr[i];
				arr[i]= arr[i + 1];
				arr[i + 1]= tmp;
				swapped = true;
			}
		}		
	}
}

int main()
{
	int values[5] = {3,2,5,4, 1};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	bubbleSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/Algorithms/Sorting/Bubble_sort