버블 정렬(Bubble Sort)은 자료 구조를 순차적으로 순회하며 인접한 요소들을 비교하여 정렬 조건에 맞지 않으면 교환하면서 정렬을 수행하는 알고리즘이다. 버블 정렬은 정렬 속도가 느려 잘 사용되지 않지만, 구현이 간단해 버그 발생 가능성이 적다는 특징이 있다.
알고리즘
버블 정렬은 다음과 같은 과정으로 이루어 진다.
- 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교한다.
- 인접한 두 요소가 정렬 조건에 맞지 않으면 교환한다.
- 반복 횟수를 i라고 정의했을 때, n - i 번째 요소까지 비교한다.
- 위 과정을 n - i = 1이 될 때까지 반복한다.
▶ 버블 정렬은 자료구조를 한 번 순회할 때마다 정렬해야 하는 범위가 하나씩 줄어든다. 이는 한번 순회할 때 마다 맨 마지막 요소가 정렬이 완료되기 때문이다.
구현
[일반적인 버블 정렬 코드]
void BubbleSort(int array[], int size)
{
for (int i = size - 1; 0 <= i; i--)
{
for (int j = 0; j < i; j++)
{
if (array[j + 1] < array[j]) // 정렬 조건
Swap(&array[j], &array[j + 1]);
}
}
}
[최적화 버블 정렬 코드]
일반적으로 구현된 버블 정렬은 요소들이 이미 정렬되어 있더라도 모든 비교가 이루어져 비효율적이다. 이를 보완하기 위해, 첫 번째 순회에서 요소의 교환이 한 번도 이루어지지 않았다면 정렬이 완료된 것으로 판단하고 종료하는 방식을 사용한다.
void OptmBubbleSort(int array[], int size)
{
for (int i = size - 1; 0 <= i; i--)
{
bool isSwap = false;
for (int j = 0; j < i; j++)
{
if (array[j + 1] < array[j])
{
Swap(&array[j], &array[j + 1]);
isSwap = true;
}
}
// 반복문이 종료 된 이후 원소의 교환이 한번도 일어나지 않았다면
// 정렬이 완료된 것으로 판단하고 종료한다.
if (!isSwap) break;
}
}
성능 측정
[시간 복잡도]
- 평균의 경우 (Average Case) : O(N2)
- 최선의 경우 (Best Case) : O(N)
최선의 경우 첫 번째 순회에서 요소의 교환이 한 번도 이루어지지 않았다면 정렬이 완료된 것으로 판단하고 정렬을 종료하기 때문에 O(N)의 시간 복잡도를 가진다. - 최악의 경우 (Worst Case) : O(N2)
내용을 적어주세요.
[공간 복잡도]
버블 정렬은 정렬하고자 하는 자료 구조 안에서 요소의 교환을 통해 정렬이 수행되는 제자리 정렬(In-Place Sort) 방식으로, 별도의 추가 공간을 사용하지 않기 때문에 O(N)의 공간 복잡도를 가진다.
[안정성]
버블 정렬은 중복된 값들을 입력 순서와 같게 정렬하는 안정적인(Stable) 정렬이다.
정리
| 장점 | 단점 |
| 구현이 간단하다. 제자리 정렬이다. In-Place Sort 안정 정렬이다. Stable Sort |
순회, 교환과 같은 연산 횟수가 많아 비효율적이다. (정렬 중 가장 비효율적) |
