버블 정렬(Bubble Sort)이란?
버블 정렬은 가장 기본적인 정렬 알고리즘 중 하나입니다. 인접한 두 요소를 반복적으로 비교하고, 순서가 올바르지 않으면 서로 교환(swap)하는 방식으로 동작하는 비교 기반 알고리즘입니다. 큰 값이 마치 물속의 거품이 위로 떠오르듯 배열의 끝으로 이동한다고 하여 '버블' 정렬이라는 이름이 붙었습니다.
버블 정렬 동작 과정 살펴보기
다음과 같이 5개의 요소를 가진 int 배열이 있다고 가정해 보겠습니다.
int[] arr = { 78, 55, 45, 98, 13 };
이제 이 배열에 버블 정렬을 단계별로 적용해 보겠습니다.
1단계: 첫 번째 두 요소인 78과 55를 비교합니다. 55가 78보다 작으므로 두 값을 교환합니다.
55, 78, 45, 98, 13
2단계: 다음으로 78과 45를 비교합니다. 45가 더 작으므로 교환합니다.
55, 45, 78, 98, 13
3단계: 78과 98을 비교합니다. 98이 더 크므로 그대로 둡니다.
4단계: 98과 13을 비교합니다. 13이 더 작으므로 교환합니다.
55, 45, 78, 13, 98
이것이 첫 번째 반복(iteration)의 결과입니다. 한 번의 반복이 끝나면 가장 큰 값인 98이 배열의 맨 끝으로 이동하게 됩니다.
이러한 반복을 모두 수행하고 나면 버블 정렬을 통해 최종적으로 다음과 같은 정렬된 배열을 얻을 수 있습니다.
13, 45, 55, 78, 98
C# 버블 정렬 예제 코드
아래는 C#으로 구현한 버블 정렬의 전체 예제 코드입니다. 중첩 for 문을 사용해 인접한 요소들을 반복적으로 비교하고 교환하는 방식을 확인할 수 있습니다.
using System;
namespace BubbleSort {
class MySort {
static void Main(string[] args) {
int[] arr = { 78, 55, 45, 98, 13 };
int temp;
for (int j = 0; j <= arr.Length - 2; j++) {
for (int i = 0; i <= arr.Length - 2; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
}
Console.WriteLine("Sorted:");
foreach (int p in arr)
Console.Write(p + " ");
Console.Read();
}
}
}
실행 결과
Sorted: 13 45 55 78 98
버블 정렬의 시간 복잡도
버블 정렬은 두 개의 중첩 반복문을 사용하기 때문에 평균 및 최악의 경우 시간 복잡도가 O(n²)입니다. 따라서 데이터 양이 많은 경우에는 비효율적일 수 있지만, 구현이 매우 간단하고 직관적이어서 알고리즘 학습용으로 널리 사용됩니다. 또한 같은 값의 상대적 순서가 유지되는 안정 정렬(stable sort)이며, 이미 정렬된 배열에 대해서는 스왑 발생 여부를 검사하는 방식으로 최적화하여 O(n)의 성능을 얻을 수도 있습니다.