버블 정렬

Q: 버블 정렬의 시간 복잡도는 무엇인가요?

버블 정렬은 중첩 루프 때문에 평균과 최악의 경우 `O(n²)` 시간에 실행됩니다. 조기 종료 최적화를 사용하면 이미 정렬된 배열에서 `O(n)`에 도달할 수 있습니다. 추가 공간은 `O(1)`을 사용합니다.

Q: 버블 정렬과 삽입 정렬의 차이는 무엇인가요?

둘 다 `O(n²)`에 실행되며 안정적이고 제자리 정렬이지만 데이터를 옮기는 방식이 다릅니다. 버블 정렬은 순서가 잘못된 인접 쌍을 반복해서 교환하고, 삽입 정렬은 각 원소를 꺼내 정렬된 앞부분의 올바른 위치로 밀어 넣습니다. 삽입 정렬은 보통 쓰기 횟수가 적고, 특히 거의 정렬된 데이터에서 실제로 더 빠릅니다.

Q: quicksort 대신 버블 정렬을 언제 사용해야 하나요?

실제 작업에서는 거의 없습니다. quicksort의 평균 시간 `O(n log n)`은 아주 작은 입력을 제외한 모든 경우에서 버블 정렬의 `O(n²)`을 압도합니다. 버블 정렬은 리스트가 매우 작거나 거의 정렬되어 있을 때, 또는 교육용으로 가능한 한 단순한 안정 정렬이 필요할 때만 쓸 가치가 있습니다.

Q: 조기 종료 최적화가 버블 정렬의 최악의 경우를 바꾸나요?

아니요. 패스에서 교환이 있었는지 추적하면 버블 정렬은 일찍 멈춰 이미 정렬된 입력에서 `O(n)`에 도달할 수 있지만, 역순으로 정렬된 배열은 여전히 모든 비교가 필요하므로 최악의 경우는 `O(n²)`로 유지됩니다. 이 최적화는 최선의 경우와 거의 정렬된 경우에만 도움이 됩니다.

마지막 업데이트 2026년 7월 1일

버블 정렬은 리스트를 반복해서 훑으며 인접한 각 원소 쌍을 비교하고, 순서가 잘못되어 있으면 교환합니다. 한 번의 전체 패스가 끝날 때마다 남은 값 중 가장 큰 값이 끝의 올바른 위치로 "떠오르므로", 각 패스는 원소를 하나씩 덜 살펴봅니다. 위의 재생을 눌러 비교와 교환을 관찰하거나 한 단계씩 진행해 보세요.

가장 이해하기 쉬운 정렬 알고리즘 중 하나여서 첫 알고리즘으로 훌륭하지만, O(n²)의 실행 시간 때문에 큰 입력에는 실용적이지 않습니다.

시간 및 공간 복잡도

경우	복잡도	비고
최선의 경우	O(n)	이미 정렬됨, 조기 종료 검사 포함
평균의 경우	O(n²)	무작위 순서
최악의 경우	O(n²)	역순 정렬
공간	O(1)	제자리, 임시 변수 하나뿐
안정성	예	같은 원소는 상대적 순서를 유지함

단계별 설명

단계	무슨 일이 일어나는가
1	배열의 처음에서 시작합니다.
2	현재 원소를 다음 원소와 비교합니다.
3	순서가 잘못되어 있으면 교환합니다.
4	한 칸 오른쪽으로 이동해 끝까지 반복합니다(한 번의 패스).
5	패스를 반복합니다. 각 패스마다 끝에서 원소가 하나씩 더 확정됩니다.
6	전체 패스에서 교환이 하나도 없으면 멈춥니다.

예제 풀이

[5, 2, 4, 1] 정렬:

패스	배열	동작
1	`[2, 4, 1, 5]`	`5,2`, 그다음 `5,4`, 그다음 `5,1`을 교환합니다. `5`가 끝으로 떠오릅니다.
2	`[2, 1, 4, 5]`	`2,4`는 순서가 맞고, `4,1`을 교환하며, `4,5`는 순서가 맞습니다. 이제 `4`가 확정됩니다.
3	`[1, 2, 4, 5]`	`2,1`을 교환합니다. 나머지는 이미 순서가 맞습니다. `2`가 확정됩니다.
4	`[1, 2, 4, 5]`	전체 패스에서 교환이 하나도 없으므로 배열은 정렬되었고 알고리즘이 멈춥니다.

버블 정렬을 언제 사용하는가

사용하면 좋을 때	피해야 할 때
비교 기반 정렬의 작동 방식을 가르치거나 배울 때	`O(n²)`이 너무 느린 큰 입력을 정렬할 때
입력이 아주 작거나 거의 정렬되어 있을 때(조기 종료 시 `O(n)`에 가까워짐)	가장 빠른 범용 정렬이 필요할 때 — quicksort나 merge sort를 사용
코드가 거의 없이 안정적이고 제자리인 정렬을 원할 때	데이터가 무작위 순서이고 성능이 중요할 때
짧은 리스트가 한 번의 패스로 이미 정렬되었는지 감지할 때	쓰기 횟수가 많으면 비용이 클 때(예: 플래시 메모리); 선택 정렬이 교환이 더 적음

Bubble Sort 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Bubble Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Bubble Sort 코드Python
1def bubble_sort(a):2    n = len(a)3    for i in range(n - 1):4        swapped = False5        for j in range(n - 1 - i):6            if a[j] > a[j + 1]:7                a[j], a[j + 1] = a[j + 1], a[j]8                swapped = True9        if not swapped:10            break  # no swaps means the list is already sorted11    return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Bubble Sort 코드JavaScript
1function bubbleSort(a) {2    for (let end = a.length - 1; end > 0; end--) {3        let swapped = false;4        for (let j = 0; j < end; j++) {5            if (a[j] > a[j + 1]) {6                [a[j], a[j + 1]] = [a[j + 1], a[j]];7                swapped = true;8            }9        }10        if (!swapped) break; // Already sorted: stop early11    }12    return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Bubble Sort 코드Java
1import java.util.Arrays;2
3public class Main {4    static void bubbleSort(int[] arr) {5        for (int i = arr.length - 1; i > 0; i--) {6            boolean swapped = false;7            for (int j = 0; j < i; j++) {8                if (arr[j] > arr[j + 1]) {9                    int tmp = arr[j];10                    arr[j] = arr[j + 1];11                    arr[j + 1] = tmp;12                    swapped = true;13                }14            }15            if (!swapped) break; // already sorted16        }17    }18
19    public static void main(String[] args) {20        int[] arr = {5, 1, 4, 2, 8, 3};21        System.out.println("Before: " + Arrays.toString(arr));22        bubbleSort(arr);23        System.out.println("After:  " + Arrays.toString(arr));24    }25}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Bubble Sort 코드C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11    for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12        bool swapped = false;13        // Each pass bubbles the largest remaining value to the end14        for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15            if (a[j] > a[j + 1]) {16                std::swap(a[j], a[j + 1]);17                swapped = true;18            }19        }20        if (!swapped) break;  // already sorted21    }22}23
24int main() {25    std::vector<int> data = {5, 1, 4, 2, 8, 3};26    std::cout << "Before: ";27    printVec(data);28    bubbleSort(data);29    std::cout << "After:  ";30    printVec(data);31    return 0;32}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Bubble Sort 코드C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void bubbleSort(int a[], int n) {10    for (int pass = 0; pass < n - 1; pass++) {11        bool swapped = false;12        // Each pass bubbles the largest remaining value to the end13        for (int j = 0; j < n - 1 - pass; j++) {14            if (a[j] > a[j + 1]) {15                int tmp = a[j];16                a[j] = a[j + 1];17                a[j + 1] = tmp;18                swapped = true;19            }20        }21        if (!swapped) break;  // already sorted22    }23}24
25int main(void) {26    int data[] = {5, 1, 4, 2, 8, 3};27    int n = sizeof(data) / sizeof(data[0]);28    printf("Before: ");29    printArr(data, n);30    bubbleSort(data, n);31    printf("After:  ");32    printArr(data, n);33    return 0;34}
이 코드를 C 플레이그라운드에서 실행하기

버블 정렬 자주 묻는 질문

버블 정렬의 시간 복잡도는 무엇인가요?

버블 정렬은 중첩 루프 때문에 평균과 최악의 경우 O(n²) 시간에 실행됩니다. 조기 종료 최적화를 사용하면 이미 정렬된 배열에서 O(n)에 도달할 수 있습니다. 추가 공간은 O(1)을 사용합니다.

버블 정렬은 안정적인가요?

예. 버블 정렬은 인접한 원소가 엄격히 순서가 잘못되었을 때만 교환하므로, 같은 원소는 서로를 지나치지 않고 원래의 상대적 순서를 유지합니다.

왜 버블 정렬이라고 부르나요?

각 패스마다 정렬되지 않은 가장 큰 값이 거품이 수면으로 떠오르듯 한 단계씩 배열의 끝으로 이동하기 때문에 "버블(거품)" 정렬이라고 부릅니다.

버블 정렬과 삽입 정렬의 차이는 무엇인가요?

둘 다 O(n²)에 실행되며 안정적이고 제자리 정렬이지만 데이터를 옮기는 방식이 다릅니다. 버블 정렬은 순서가 잘못된 인접 쌍을 반복해서 교환하고, 삽입 정렬은 각 원소를 꺼내 정렬된 앞부분의 올바른 위치로 밀어 넣습니다. 삽입 정렬은 보통 쓰기 횟수가 적고, 특히 거의 정렬된 데이터에서 실제로 더 빠릅니다.

quicksort 대신 버블 정렬을 언제 사용해야 하나요?

실제 작업에서는 거의 없습니다. quicksort의 평균 시간 O(n log n)은 아주 작은 입력을 제외한 모든 경우에서 버블 정렬의 O(n²)을 압도합니다. 버블 정렬은 리스트가 매우 작거나 거의 정렬되어 있을 때, 또는 교육용으로 가능한 한 단순한 안정 정렬이 필요할 때만 쓸 가치가 있습니다.

조기 종료 최적화가 버블 정렬의 최악의 경우를 바꾸나요?

아니요. 패스에서 교환이 있었는지 추적하면 버블 정렬은 일찍 멈춰 이미 정렬된 입력에서 O(n)에 도달할 수 있지만, 역순으로 정렬된 배열은 여전히 모든 비교가 필요하므로 최악의 경우는 O(n²)로 유지됩니다. 이 최적화는 최선의 경우와 거의 정렬된 경우에만 도움이 됩니다.