버블 정렬 (Bubble Sort)

1. 작동 방식

버블 정렬은 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 조건이 맞지 않다면 두 원소를 교환하는 동작을 순차적으로 반복하여 오른쪽부터 차례대로 원소들이 정렬되게 하는 정렬 알고리즘이다.

출처 : https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/resources/bubble-sort-001.gif

위의 그림처럼 버블 정렬 시 정렬된 원소의 부분 집합과 아직 정렬되지 않은 원소의 부분 집합으로 나뉜다. 버블되어 올라간 원소들이 차례대로 오른쪽으로 옮겨져 정렬된 부분 집합을 이룬다. 정렬되지 않은 부분 집합들의 원소들에 대하여 설명한 동작을 전체 원소가 정렬될 때까지 반복한다.

2. 구현

// 구현부
void BubbleSort(int* arr, int size)
{
	for (int i = size - 1; i >= 1; --i)
	{
    	// 교환이 일어나는지 체크
		bool Swapped = false;

		for (int j = 0; j < i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				std::swap(arr[j], arr[j + 1]);
				Swapped = true;
			}
		}
		
        // 교환이 일어나지 않았다면 모두 정렬됐다는 뜻이므로 break
		if (!Swapped) break;
	}
}

// 실행부
int main()
{
	int arr[]{ 5, 4, 3, 2, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    BubbleSort(arr, size);
    for (const auto& ele : arr)
    {
    	std::cout << ele << " ";
    }
    
    // 출력 : 1 2 3 4 5
}

3. 시간 복잡도 / 공간 복잡도

- 시간 복잡도

최선 : $O(n)$

배열이 이미 정렬된 상태면 한 번만 순회하면 되기 때문에 최선일 때의 시간 복잡도는 $O(n)$이다.

평균, 최악 : $O(n^2)$

인접한 두 원소를 비교하고 교환하는 횟수가 총 $(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2$ 이고, 배열이 역순인 최악의 상황일 때도 마찬가지이므로 시간 복잡도는 $O(n^2)$이다.

- 공간 복잡도

버블 정렬은 추가적인 배열이나 메모리를 사용하지 않고 배열 내에서 원소의 교환이 이루어지기 때문에 공간 복잡도는 $O(1)$이다.

4. 장점 / 단점

- 장점

1. 원리가 단순하며 구현이 쉽다.
2. 안정적 정렬(stable sort)이므로 정렬된 데이터의 값이 같더라도 순서가 보장된다.
3. 제자리 정렬(In-place Sorting)이기 때문에 추가적인 메모리를 필요로 하지 않는다.

- 단점

1. 원소가 제자리를 찾아갈 때 교환이 많이 일어난다.
2. 주어진 데이터의 크기가 클 경우 다른 정렬 알고리즘에 비해 비효율적이다.