Bubble Sort(버블 정렬)는 배열에서 인접한 두 원소를 비교하고, 순서가 잘못된 경우 교환(Swap)을 반복하여 정렬하는 비교 기반 정렬 알고리즘입니다. 구현이 단순하고 동작이 직관적이기 때문에, 정렬 알고리즘을 이해할 때 “비교 횟수/교환 횟수” 관점에서 비용 구조를 확인하기에 적합한 기준점입니다.
Bubble Sort는 한 번의 패스(Pass)가 끝날 때마다 현재 구간에서 가장 큰 값이 배열의 뒤쪽으로 확정되는 성질을 가집니다. 이 특성 때문에 패스가 진행될수록 비교 범위가 점점 줄어듭니다. 다만 비교 흐름이 (N-1) + (N-2) + ... + 1 형태로 누적되므로, 입력 크기 N이 커질수록 비교 비용이 빠르게 증가하여 시간 복잡도는 O(N²) 구조가 됩니다.
이번 글에서는 Bubble Sort의 개념과 패스 단위 동작 원리를 정리하고, C#으로 기본 구현과 최적화 구현(교환 여부 플래그)을 작성한 뒤, Unity 테스트 코드로 실행 흐름을 확인해 보겠습니다.
1. Bubble Sort의 구조와 동작 방식
Bubble Sort는 “정렬을 인접 교환만으로 해결한다”는 매우 제한적인 규칙을 사용합니다. 즉, 멀리 떨어진 두 값의 위치를 한 번에 바꾸지 않고, 잘못된 순서를 발견할 때마다 한 칸씩 이동시키며 정렬 상태를 만들어 냅니다. 이 단순함이 장점이자 한계이며, 비교/교환이 많은 이유도 여기에서 발생합니다.
1.1 기본 아이디어: 인접 원소 비교
- 배열에서 인접한 두 원소
(values[i], values[i+1])를 비교합니다. - 오름차순 기준으로
values[i] > values[i+1]이면 두 값을 교환합니다. - 이를 배열 끝까지 반복하면, 큰 값이 점점 오른쪽으로 “밀려” 이동합니다.
이 방식의 핵심은 “정렬 상태를 만들기 위해 필요한 최소 단위의 수정”만 수행한다는 점입니다. 비교 후 교환이 발생하면, 큰 값이 오른쪽으로 한 칸 이동합니다. 이 이동이 반복되며 결국 큰 값이 뒤쪽으로 확정됩니다.
1.2 Pass(패스)가 끝나면 어떤 상태가 되는가
버블 소트는 바깥 루프 1회(= Pass 1회)가 끝날 때마다 다음 상태가 됩니다.
- 현재 비교 대상 구간에서 최댓값이 맨 뒤로 이동하여 확정됩니다.
- 따라서 다음 Pass에서는 이미 확정된 뒤쪽 원소를 다시 비교할 필요가 없습니다.
이 특성 때문에 Pass passIndex가 증가할수록 내부 비교 범위는 length - 1 - passIndex로 줄어듭니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Bubble Sort의 인접한 두 값을 비교하고 교환(Swap)하며 정렬이 진행되는 과정을 단계별로 시각화해 주는 도구입니다. 각 패스(pass)가 끝날 때마다 가장 큰 값이 배열의 뒤쪽으로 이동하는 모습을 직관적으로 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 왜 O(N²)이 되는가 (비교 흐름 기준)
Bubble Sort의 비용을 “빠르다/느리다”로 설명하기보다, 비교 횟수 흐름으로 보면 구조가 분명해집니다.
- 길이가 N이면 Pass 1은 N-1번 비교
- Pass 2는 N-2번 비교
- ...
- 마지막은 1번 비교
비교 횟수는 (N-1) + (N-2) + … + 1 = N(N-1) / 2 형태로 누적되며, 이는 대략 N2/2 수준으로 증가합니다. 따라서 입력 크기 N이 커질수록 비교 비용은 O(N2) 구조를 가집니다.
3. 이미 정렬된 경우에도 비효율적인 이유
기본 버블 소트는 배열이 이미 정렬된 상태여도 “정렬이 완료되었는지”를 판단할 장치가 없습니다. 따라서 교환이 단 한 번도 발생하지 않더라도, 모든 Pass를 끝까지 수행하며 비교를 반복합니다.
즉 “교환은 없지만 비교는 계속 발생”하는 형태가 되며, 입력이 이미 정렬된 경우에도 불필요한 비교 비용이 그대로 남습니다.
4. 최적화: 교환 여부 플래그(swap flag)
위 문제를 줄이기 위한 가장 대표적인 최적화는 한 Pass 동안 교환이 있었는지를 기록하는 방식입니다.
- Pass 동안 한 번이라도 교환이 발생하면
didSwap = true - Pass 종료 시점에
didSwap == false라면 배열은 이미 정렬된 상태이므로 즉시 종료
이 최적화는 최악의 경우(O(N²))를 바꾸지는 못하지만, 이미 정렬되어 있거나 거의 정렬된 입력에서 불필요한 Pass를 줄여 비교 횟수를 크게 감소시킬 수 있습니다.
5. 실행 흐름을 예제로 확인하기
예제 배열을 다음과 같이 두고, SortWithSwapFlag 기준으로 “실행 흐름(비교/교환/패스 종료)”이 어떻게 진행되는지 단계별로 확인합니다.
- 정렬 전: [5, 1, 4, 2, 8]
표기 규칙
- passIndex: 현재 Pass 번호(0부터 시작)
- lastCompareIndex = length - 1 - passIndex: 이번 Pass에서 비교할 마지막 인덱스
- 각 비교는 (values[i], values[i+1]) 형태로 수행
5.1 Pass 1 (passIndex = 0)
Pass 1에서는 lastCompareIndex = 5 - 1 - 0 = 4이므로, i = 0..3까지 총 4번 인접 비교가 발생합니다.
- 비교: (5, 1) → 5 > 1 이므로 교환
배열: [1, 5, 4, 2, 8]
didSwap = true - 비교: (5, 4) → 5 > 4 이므로 교환
배열: [1, 4, 5, 2, 8] - 비교: (5, 2) → 5 > 2 이므로 교환
배열: [1, 4, 2, 5, 8] - 비교: (5, 8) → 5 > 8 아님(교환 없음)
배열: [1, 4, 2, 5, 8]
Pass 1이 종료되면, 현재 구간의 최댓값 8은 배열의 맨 뒤에 위치하며 이 값은 이후 Pass에서 비교 대상에서 제외됩니다.
5.2 Pass 2 (passIndex = 1)
Pass 2에서는 lastCompareIndex = 5 - 1 - 1 = 3이므로, i = 0..2까지 총 3번 비교합니다. 이 Pass가 끝나면 뒤에서 두 번째 값이 확정됩니다.
- 비교: (1, 4) → 1 > 4 아님(교환 없음)
배열: [1, 4, 2, 5, 8] - 비교: (4, 2) → 4 > 2 이므로 교환
배열: [1, 2, 4, 5, 8]
didSwap = true - 비교: (4, 5) → 4 > 5 아님(교환 없음)
배열: [1, 2, 4, 5, 8]
Pass 2 종료 시점에서 뒤쪽 [5, 8] 구간은 확정 상태로 볼 수 있습니다.
5.3 Pass 3 (passIndex = 2) - 조기 종료 조건 확인
Pass 3에서는 lastCompareIndex = 5 - 1 - 2 = 2이므로, i = 0..1까지 총 2번 비교합니다. 현재 배열은 이미 정렬 상태이므로, 이 Pass에서 교환이 발생하지 않습니다.
- 비교: (1, 2) → 교환 없음
배열: [1, 2, 4, 5, 8] - 비교: (2, 4) → 교환 없음
배열: [1, 2, 4, 5, 8]
이번 Pass에서 didSwap이 한 번도 true가 되지 않았으므로, if (didSwap == false) { break; }에 의해 정렬이 즉시 종료됩니다.
정렬 결과: [1, 2, 4, 5, 8]
6. C# 기반 Bubble Sort 직접 구현 코드
정렬 알고리즘은 자료구조(Collections)와 책임이 다르므로, 다음 네임스페이스로 분리합니다.
Daebak.Common.Algorithms.Sorting
아래 코드는 기본 구현과 최적화 구현을 모두 포함합니다.
using System;
namespace Daebak.Common.Algorithms.Sorting
{
/// <summary>
/// Bubble Sort (오름차순)
/// 인접한 두 원소를 반복적으로 비교하여 큰 값을 뒤로 이동시키는 정렬 알고리즘
/// </summary>
public static class BubbleSort
{
/// <summary>
/// 기본 버블 소트
/// 모든 Pass를 끝까지 수행한다.
/// </summary>
public static void SortBasic(int[] values)
{
if (values == null)
{
throw new ArgumentNullException(nameof(values));
}
int length = values.Length;
if (length <= 1)
{
return;
}
for (int passIndex = 0; passIndex < length - 1; passIndex++)
{
int lastCompareIndex = length - 1 - passIndex;
for (int i = 0; i < lastCompareIndex; i++)
{
if (values[i] > values[i + 1])
{
int temp = values[i];
values[i] = values[i + 1];
values[i + 1] = temp;
}
}
}
}
/// <summary>
/// 최적화된 버블 소트
/// 한 Pass에서 교환이 발생하지 않으면 즉시 종료한다.
/// </summary>
public static void SortWithSwapFlag(int[] values)
{
if (values == null)
{
throw new ArgumentNullException(nameof(values));
}
int length = values.Length;
if (length <= 1)
{
return;
}
for (int passIndex = 0; passIndex < length - 1; passIndex++)
{
bool didSwap = false;
int lastCompareIndex = length - 1 - passIndex;
for (int i = 0; i < lastCompareIndex; i++)
{
if (values[i] > values[i + 1])
{
int temp = values[i];
values[i] = values[i + 1];
values[i + 1] = temp;
didSwap = true;
}
}
if (didSwap == false)
{
break;
}
}
}
}
}7. Unity 환경에서 테스트 해보기
아래 코드는 Unity Start()에서 버블 소트를 실행하고, 정렬 전/후 배열을 로그로 출력합니다. 알고리즘 코드는 Unity와 분리되어 있으며, Unity 스크립트는 호출과 출력만 담당합니다.
using UnityEngine;
using Daebak.Common.Algorithms.Sorting;
public class Test_BubbleSort : MonoBehaviour
{
private void Start()
{
int[] values = new int[] { 5, 1, 4, 2, 8 };
Debug.Log("Before Sort : " + string.Join(", ", values));
BubbleSort.SortWithSwapFlag(values);
Debug.Log("After Sort : " + string.Join(", ", values));
}
}
실행 결과
Before Sort : 5, 1, 4, 2, 8
After Sort : 1, 2, 4, 5, 8마무리
Bubble Sort는 인접 비교/교환만으로 정렬을 구성하는 단순한 알고리즘이며, 한 Pass가 끝날 때마다 최댓값이 뒤쪽으로 확정되는 특징을 가집니다. 비교 횟수는 (N-1) + (N-2) + ... + 1로 누적되기 때문에, 입력이 커질수록 O(N²) 구조로 비용이 증가합니다.
기본 구현은 이미 정렬된 입력에서도 모든 Pass를 수행하여 불필요한 비교가 발생할 수 있습니다. 이를 줄이기 위해 교환 여부 플래그를 사용하면, 교환이 없는 Pass에서 조기 종료가 가능해져 이미 정렬된 경우의 비교 비용을 크게 줄일 수 있습니다.
정렬 알고리즘을 학습하거나 정리할 때는 실행 시간이 빠르다/느리다보다, 비교가 몇 번 발생하는지, 교환이 어떤 조건에서 발생하는지를 기준으로 구조를 이해하는 것이 더 중요합니다. 이러한 관점에서 Bubble Sort는 다른 정렬 알고리즘들과의 비용 구조를 비교할 때 기준점으로 삼기 좋은 알고리즘입니다.
※ 다음 글에서는 Selection Sort를 살펴보며, 전체 구간에서 최소(또는 최대) 값을 선택해 한 번의 교환으로 위치를 확정하는 방식이 비교 횟수와 교환 비용을 어떻게 분리하는지를 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Insertion Sort(삽입 정렬) 구현 (0) | 2026.01.14 |
|---|---|
| Unity 개발자를 위한 C# Selection Sort(선택 정렬) 구현 (0) | 2026.01.14 |
| Unity 개발자를 위한 정렬(Sort) 개념과 시간 복잡도 이해 (0) | 2026.01.13 |
| Unity 개발자를 위한 시간 복잡도(Big O) 개념 정리 (0) | 2026.01.13 |
| Unity 개발자를 위한 C# Red-Black Tree(레드 블랙 트리) 구현 (0) | 2025.12.27 |
