Bubble Sort(버블 정렬)

버블정렬은 앞에 있는 값과 뒤에 있는 값을 비교하여 내가 원하는 순서대로 정렬하는 것을 뜻합니다.

버블정렬 특성상 내가 정렬하고자하는 값이 맨 뒤로 차곡차곡 옮겨지기에 Selection Sort와는 반대로 정렬이 끝난 뒤에 있는 값을 신경써줄 필요가 없다.

선택정렬과 마찬가지로 n*(n+1)/2의 비교횟수를 가지고, 따라서 big-O또한 O(n^2)이다.

Bubble Sort code

#include<iostream>

int main()
{
	int a[] = {5, 8, 2, 7, 4, 1, 9, 6, 3};
	int temp;

	
	for(int i = 0 ; i < 9 ; i++)
	{
		for(int j = 0 ; j < 8 - i ; j++)
		{
			if(a[j] > a[j + 1])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	
	for(int i = 0 ; i < 9 ; i++)
	{
		std::cout << a[i];
	}
	
	return 0;
}

이미지 출처
도움 자료