정렬 알고리즘(버블·삽입·퀵 정렬)

1. 개요

가. 정의

정렬 알고리즘(Sorting Algorithm) 은 주어진 데이터 집합을 사용자가 지정한 기준(오름/내림차순)에 맞게 순서대로 재배치하는 기법으로, 탐색·병합·집계 등 다른 연산의 효율을 좌우하는 가장 기초적인 알고리즘이다.

정렬은 컴퓨터과학에서 가장 오래 연구된 문제 중 하나이며, 사실상 모든 응용 시스템의 밑바닥에 깔려 있다. 데이터베이스의 인덱스 구성, 이진 탐색을 위한 사전 정렬, 중복 제거, 통계 처리의 중앙값·분위수 계산 등이 모두 정렬을 전제로 한다. 정렬이 왜 중요한가 하면, 정렬된 데이터에서는 이진 탐색으로 O(log n)의 검색이 가능해지고, 인접한 중복을 O(n)에 제거할 수 있는 등 후속 연산의 복잡도가 극적으로 낮아지기 때문이다. 반대로 정렬이 느리면 그 위에 쌓인 모든 연산이 함께 느려진다.

나. 정렬 알고리즘을 이해하는 세 축: 시간·안정성·메모리

정렬 알고리즘을 이해하는 핵심은 '시간 복잡도, 안정성, 추가 메모리 사이의 트레이드오프'다. 단순한 알고리즘(버블·삽입·선택)은 이해·구현이 쉽지만 데이터가 커지면 O(n²)로 급격히 느려지고, 분할정복 기반(퀵·병합)은 평균 O(n log n)으로 훨씬 빠르지만 구현이 복잡하거나 추가 메모리를 요구한다. 여기에 '같은 값의 상대 순서를 보존하는가(안정성)', '추가 메모리를 얼마나 쓰는가(제자리 여부)'가 더해져 상황에 맞는 선택이 달라진다.

이 트레이드오프는 추상적인 이론이 아니라 실무 선택을 직접 좌우한다. 예를 들어 데이터가 거의 정렬되어 있으면 단순한 삽입 정렬이 오히려 퀵 정렬보다 빠르고, 대용량 무작위 데이터면 퀵 정렬이 유리하며, 메모리가 극도로 제약된 임베디드 환경에서는 추가 메모리를 쓰지 않는 제자리 정렬이 강제된다. 즉 "가장 빠른 정렬"이라는 절대적 답은 없고, 데이터의 크기·초기 상태·메모리 제약·안정성 요구에 따라 최적해가 달라진다.

다. 안정성과 제자리 정렬

안정 정렬(Stable Sort) 은 값이 같은 원소들의 원래 순서를 유지하는 것으로, 다중 기준 정렬(1차로 이름순, 2차로 나이순)에서 결정적으로 중요하다. 먼저 이름으로 정렬한 뒤 나이로 다시 정렬할 때, 나이 정렬이 안정적이어야 같은 나이 안에서 이름순이 보존된다. 제자리(in-place) 정렬 은 입력 배열 외에 추가 메모리를 거의(O(1)~O(log n)) 쓰지 않는 것으로, 메모리가 제약된 환경에서 유리하다. 이 두 성질은 서로 독립적이어서, 안정하지만 추가 메모리를 쓰는 정렬(병합)과 제자리이지만 불안정한 정렬(퀵)이 모두 존재한다.

2. 정렬 알고리즘의 분류

정렬 알고리즘은 크게 비교 기반(comparison-based) 과 비비교 기반(non-comparison) 으로 나뉜다. 비교 기반은 원소를 서로 비교해 순서를 정하며, 비교 횟수의 하한이 이론적으로 O(n log n)임이 증명되어 있다. 비비교 기반(계수·기수·버킷 정렬)은 값의 분포나 자릿수를 직접 이용해 특정 조건에서 O(n)에 도달하지만, 데이터 범위 제약이 있다. 아래 분류도는 본 주제가 다루는 세 알고리즘의 위치를 보여준다.

flowchart TB
  ROOT["정렬 알고리즘"] --> CMP["비교 기반(하한 O(n log n))"]
  ROOT --> NCMP["비비교 기반(계수·기수·버킷)"]
  CMP --> SIMPLE["단순 O(n제곱)"]
  CMP --> ADV["고급 O(n log n)"]
  SIMPLE --> BUB["버블 정렬"]
  SIMPLE --> INS["삽입 정렬"]
  SIMPLE --> SEL["선택 정렬"]
  ADV --> QUICK["퀵 정렬(분할정복)"]
  ADV --> MERGE["병합 정렬(분할정복)"]
  ADV --> HEAP["힙 정렬"]

이 분류에서 버블·삽입 정렬은 단순 O(n²) 계열에, 퀵 정렬은 고급 O(n log n) 계열의 분할정복에 속한다. 단순 계열은 "왜 정렬이 어려운가"를 직관적으로 보여주는 교육적 가치가 크고, 고급 계열은 실무에서 실제로 쓰인다. 세 알고리즘을 나란히 보는 것은 O(n²)와 O(n log n)의 격차가 어디서 오는지를 이해하는 가장 좋은 방법이다.

3. 버블 정렬(Bubble Sort)

인접한 두 원소를 비교해 순서가 잘못되어 있으면 교환하는 과정을 반복하며, 큰 값이 거품처럼 배열의 뒤로 떠오르는 방식이다.

버블 정렬은 배열의 처음부터 끝까지 인접한 두 원소를 비교·교환하며 한 번 훑는다. 이 한 번의 패스(pass)가 끝나면 가장 큰 값이 맨 뒤에 확정된다. 그다음 패스는 확정된 마지막 원소를 제외하고 다시 훑어 두 번째로 큰 값을 확정하며, 이를 n-1회 반복하면 전체가 정렬된다. 이름 그대로 큰 값이 물 위의 거품처럼 뒤로 떠오르는 모습에서 유래했다.

버블 정렬의 가장 큰 특징은 구현이 가장 단순하다는 점이다. 이중 반복문과 교환(swap) 한 줄이면 완성되어 알고리즘 입문 교육에 널리 쓰인다. 그러나 매 패스마다 인접 비교·교환을 반복하므로 실제 성능은 최악이다. n개 원소에 대해 약 n²/2회의 비교와 교환이 일어나, 데이터가 조금만 커져도 급격히 느려진다.

한 가지 최적화는 한 패스에서 교환이 한 번도 일어나지 않으면 이미 정렬된 것이므로 중단하는 플래그(flag) 기법이다. 이 최적화를 적용하면 이미 정렬된 입력에 대해 O(n)에 종료할 수 있다. 하지만 무작위 데이터에서는 여전히 O(n²)이어서, 이 최적화가 있어도 버블 정렬은 실무보다 교육용으로 남는다.

• 복잡도: 시간 평균·최악 O(n²), 최선 O(n)(최적화 시), 공간 O(1), 안정 정렬
• 용도: 교육용·아주 작은 데이터. 실무 대용량 정렬에는 부적합.

4. 삽입 정렬(Insertion Sort)

정렬된 부분 배열에 새 원소를 하나씩 꺼내 올바른 위치에 끼워 넣는 방식으로, 손에 든 카드를 정렬하는 방법과 같다.

삽입 정렬은 두 번째 원소부터 시작해, 그 원소를 앞의 이미 정렬된 구간과 비교하며 알맞은 자리에 삽입한다. 삽입할 위치를 찾는 동안 그보다 큰 원소들은 한 칸씩 뒤로 밀린다. 카드 게임에서 새로 받은 카드를 손안의 정렬된 카드 사이에 끼워 넣는 동작과 정확히 같아 직관적으로 이해하기 쉽다.

삽입 정렬의 결정적 강점은 입력의 초기 상태에 민감하다는 점이다. 최악(역순 정렬)은 O(n²)이지만, 이미 거의 정렬된 데이터에서는 비교가 거의 일어나지 않아 O(n)에 근접해 매우 빠르다. 각 원소가 제자리에 가까이 있으면 뒤로 밀 원소가 거의 없기 때문이다. 이 적응적(adaptive) 성질 덕분에, 소규모 데이터나 부분 정렬된 데이터에서는 퀵 정렬보다도 실용적일 수 있다.

바로 이 특성 때문에 삽입 정렬은 실무에서 다른 정렬의 보조 도구로 쓰인다. 퀵 정렬이나 병합 정렬이 재귀적으로 배열을 잘게 쪼개다가, 부분 배열의 크기가 일정 임계값(보통 10~32) 이하로 작아지면 재귀 오버헤드가 큰 분할정복 대신 삽입 정렬로 전환한다. 작은 배열에서는 삽입 정렬의 상수 계수가 작아 오히려 빠르기 때문이다.

• 복잡도: 시간 평균·최악 O(n²), 최선 O(n), 공간 O(1), 안정 정렬
• 용도: 소규모·부분정렬 데이터, 하이브리드 정렬의 마무리 단계.

5. 퀵 정렬(Quick Sort)

피벗(pivot) 을 하나 정해 그보다 작은 값과 큰 값으로 배열을 분할하고, 각 부분을 재귀적으로 다시 정렬하는 분할정복(Divide and Conquer) 알고리즘이다.

퀵 정렬은 피벗을 기준으로 배열을 두 그룹(피벗보다 작은 값, 큰 값)으로 나누는 분할(partition) 을 수행한다. 분할이 끝나면 피벗은 최종 정렬 위치를 확정하고, 좌·우 부분 배열을 같은 방식으로 재귀 정렬하면 전체가 정렬된다. 아래 다이어그램은 분할정복이 배열을 어떻게 재귀적으로 쪼개고 합치는지를 보여준다.

flowchart TB
  A["배열: 5 3 8 1 9 2 (피벗=5)"] --> L["작은 값: 3 1 2"]
  A --> P["피벗 확정: 5"]
  A --> R["큰 값: 8 9"]
  L --> L1["피벗=3 -> 1 2 | 3"]
  R --> R1["피벗=8 -> 8 | 9"]
  L1 --> RES["병합 결과: 1 2 3 5 8 9"]
  R1 --> RES

퀵 정렬은 평균적으로 가장 빠른 정렬로 널리 쓰인다. 제자리 정렬에 가깝고(재귀 스택만 사용), 캐시 지역성이 좋아 상수 계수가 작기 때문이다. 그러나 치명적 약점이 있다. 피벗을 잘못 고르면 분할이 한쪽으로 치우쳐 최악 O(n²) 로 나빠진다. 예컨대 이미 정렬된 데이터에서 항상 첫 원소를 피벗으로 고르면, 매번 한 원소만 분리되어 n번의 분할이 필요해진다.

이 최악을 피하기 위해 실무에서는 피벗 선택 전략을 정교화한다. 배열의 세 지점(처음·중간·끝) 값의 중앙값을 피벗으로 쓰는 median-of-three, 무작위로 피벗을 고르는 randomized quicksort 가 대표적이다. 무작위화는 특정 입력이 항상 최악을 유발하는 것을 막아, 어떤 입력에서도 평균 O(n log n)을 기대할 수 있게 한다. 또 재귀 깊이가 너무 깊어지면 힙 정렬로 전환해 최악 O(n log n)을 보장하는 인트로소트(Introsort) 기법도 쓰인다.

• 복잡도: 시간 평균 O(n log n), 최악 O(n²), 공간 O(log n)(재귀 스택), 불안정 정렬
• 용도: 대용량 무작위 데이터의 범용 고속 정렬(C++ STL 등).

6. 비교 및 사례

세 알고리즘의 차이는 결국 "비교·교환을 얼마나 낭비 없이 하는가"에서 갈린다. 버블·삽입은 인접 원소만 다루므로 한 번의 비교로 원소를 멀리 보낼 수 없어 O(n²)에 머물고, 퀵 정렬은 피벗 분할로 원소를 단번에 절반 규모로 나눠 O(n log n)을 달성한다. 아래 표와 그래프는 이 차이를 정리한다.

알고리즘	평균	최악	최선	공간	안정성	핵심 특징
버블 정렬	O(n²)	O(n²)	O(n)	O(1)	안정	인접 교환, 교육용
삽입 정렬	O(n²)	O(n²)	O(n)	O(1)	안정	부분정렬에 강함, 적응적
퀵 정렬	O(n log n)	O(n²)	O(n log n)	O(log n)	불안정	분할정복, 평균 최고속

{
  "type": "bar",
  "data": {
    "labels": ["버블", "삽입", "퀵"],
    "datasets": [{
      "label": "평균 비교 연산(n=1000, 상대값)",
      "data": [1000000, 250000, 10000],
      "backgroundColor": ["#e11d48", "#f59e0b", "#2f6fed"]
    }]
  },
  "options": {
    "plugins": { "legend": { "display": false }, "title": { "display": true, "text": "평균 연산량 비교 (개념적 예시)" } },
    "scales": { "y": { "title": { "display": true, "text": "연산 횟수(상대)" } } }
  }
}

위 그래프는 n=1000일 때 O(n²) 계열(버블·삽입)과 O(n log n) 계열(퀵)의 연산량 차이가 얼마나 극적인지를 보여준다. n=1000에서 O(n²)은 약 100만, O(n log n)은 약 1만으로 100배 차이가 나며, 데이터가 커질수록 이 격차는 기하급수적으로 벌어진다. n=100만이면 O(n²)은 약 10¹²회, O(n log n)은 약 2×10⁷회로, 초당 10억 연산 기준 각각 약 1000초와 0.02초라는 실용성의 경계를 가른다.

구체적 사례로, 데이터베이스가 ORDER BY 절을 처리할 때는 메모리에 올릴 수 있으면 퀵/인트로소트 계열을, 메모리를 넘으면 디스크 기반 외부 병합 정렬(external merge sort)을 쓴다. 반대로 실시간으로 거의 정렬된 스트림(예: 로그 타임스탬프)을 유지·삽입할 때는 삽입 정렬 계열이 O(n)에 가까워 유리하다.

7. 심화: 실무 라이브러리의 하이브리드 정렬

실무에서 가장 중요한 통찰은 "단일 알고리즘을 그대로 쓰지 않는다"는 점이다. 표준 라이브러리들은 여러 알고리즘의 장점을 결합한 하이브리드 정렬을 채택한다.

자바(Arrays.sort의 객체 정렬)와 파이썬(sorted, list.sort)은 팀소트(Timsort) 를 쓴다. 팀소트는 병합 정렬과 삽입 정렬을 결합한 것으로, 데이터에 이미 정렬된 구간(run)이 있으면 이를 감지해 병합함으로써 실세계 데이터(부분적으로 정렬된 경우가 많음)에서 O(n)에 근접한다. 안정 정렬이라는 점도 다중 기준 정렬에 중요하다.

C++ STL의 std::sort는 인트로소트(Introsort) 를 쓴다. 기본은 퀵 정렬로 시작하되, 재귀 깊이가 2·log n을 넘으면(최악으로 치닫는 신호) 힙 정렬로 전환해 최악에서도 O(n log n)을 보장하고, 부분 배열이 작아지면 삽입 정렬로 마무리한다. 즉 퀵의 평균 속도, 힙의 최악 보장, 삽입의 소규모 효율을 모두 취한다.

이 하이브리드 설계는 앞서 본 트레이드오프를 실전에서 어떻게 종합하는지를 보여준다. 어떤 단일 알고리즘도 모든 상황에서 최적일 수 없으므로, 데이터의 크기·초기 상태에 따라 알고리즘을 동적으로 전환해 "평균 성능, 최악 보장, 안정성"을 함께 확보하는 것이다. 정보관리기술사 관점에서 정렬을 논할 때는 개별 알고리즘의 복잡도 암기를 넘어, 이처럼 요구사항에 따라 알고리즘을 조합·선택하는 설계 판단까지 다룰 수 있어야 한다.

8. 고려사항 및 시사점

1. 절대적 최적해는 없다(상황 적합성): 데이터의 크기·초기 상태·메모리 제약·안정성 요구에 따라 최적 정렬이 달라진다. 거의 정렬된 소규모 데이터는 삽입, 대용량 무작위는 퀵, 안정성이 필요하면 병합/팀소트가 적합하다.
2. 퀵 정렬의 최악 O(n²) 회피(견고성): 피벗을 무작위 또는 median-of-three로 고르고, 재귀 깊이 초과 시 힙 정렬로 전환(인트로소트)해 최악을 방어해야 한다. 정렬 대상이 외부 입력이라면 악의적 최악 유발(알고리즘 복잡도 공격) 가능성까지 고려한다.
3. 안정성 요구의 식별(정확성): 다중 기준 정렬이나 순서 보존이 필요한 업무에서는 불안정한 퀵 정렬 대신 안정 정렬(병합·팀소트)을 선택해야 결과가 의도대로 나온다.
4. 메모리 제약 환경의 선택(자원 효율): 임베디드·대용량 환경에서는 추가 메모리 사용량이 관건이다. 제자리 정렬(퀵·힙)과 외부 정렬(디스크 기반 병합)을 데이터가 메모리에 들어가는지 여부로 구분해 선택한다.
5. 라이브러리 신뢰와 검증(실무 원칙): 특별한 이유가 없으면 검증된 표준 라이브러리(팀소트·인트로소트)를 쓰는 것이 안전하다. 직접 구현은 경계·중복·최악 케이스에서 버그가 잦으므로, 성능 요구가 명확할 때만 최적화 구현을 고려한다.

참고자료

• Cormen et al., "Introduction to Algorithms", MIT Press (분할정복·정렬 하한)
• CPython Timsort listsort 설명: https://github.com/python/cpython/blob/main/Objects/listsort.txt
• cppreference std::sort(Introsort): https://en.cppreference.com/w/cpp/algorithm/sort

---

한 줄 요약: 버블·삽입 정렬은 O(n²)의 단순 정렬(삽입은 거의 정렬된 데이터에 적응적으로 효율적)이고 퀵 정렬은 평균 O(n log n)의 분할정복 으로 빠르나 피벗에 따라 최악 O(n²)이며, 안정성·데이터 특성·메모리 제약에 따라 병합 정렬이나 하이브리드(팀소트·인트로소트)를 선택하는 설계 판단이 핵심이다.