GM 오락실
← 개인 공부 · Algorithm
STUDY NOTE · 개념 정리

정렬 알고리즘 비교 정리: 버블·선택·삽입·병합·퀵·힙 정렬과 안정 정렬

Algorithm
정렬 알고리즘은 시간 복잡도, 추가 메모리, 안정성 세 가지로 비교한다. O(n²) 정렬(버블·선택·삽입)은 단순하지만 느리고, O(n log n) 정렬(병합·퀵·힙)이 실전용이다. 비교 기반 정렬은 O(n log n)보다 빠를 수 없다.

1. 한눈에 비교

알고리즘최선평균최악추가 공간안정
버블 정렬O(n)*O(n²)O(n²)O(1)O
선택 정렬O(n²)O(n²)O(n²)O(1)X
삽입 정렬O(n)O(n²)O(n²)O(1)O
병합 정렬O(n log n)O(n log n)O(n log n)O(n)O
퀵 정렬O(n log n)O(n log n)O(n²)O(log n) (재귀 스택)X
힙 정렬O(n log n)O(n log n)O(n log n)O(1)X
계수 정렬O(n + k)O(n + k)O(n + k)O(n + k)O (구현에 따라)

* 버블 정렬의 O(n)은 한 바퀴 동안 교환이 없으면 멈추는 최적화를 넣었을 때다. 계수 정렬의 k는 값의 범위다.

2. O(n²) 정렬

알고리즘아이디어특징
버블이웃한 두 원소를 비교해 큰 것을 뒤로 보냄. 한 바퀴마다 가장 큰 값이 끝에 확정교환이 많아 가장 느린 편
선택남은 구간에서 최솟값을 찾아 맨 앞과 교환교환 횟수가 최대 n-1번으로 적음, 멀리 떨어진 원소끼리 교환해 불안정
삽입앞쪽 정렬된 구간에 현재 원소를 알맞은 자리에 끼워 넣음거의 정렬된 데이터에서 O(n)에 가까움, 작은 배열에서 빠름
void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) { // 큰 원소를 한 칸씩 뒤로
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}

a[j] > key처럼 같은 값은 넘어가지 않으므로 삽입 정렬은 안정 정렬이다. 조건을 >=로 바꾸면 안정성이 깨진다.

3. O(n log n) 정렬

알고리즘아이디어장점단점
병합 정렬반으로 나눠 각각 정렬한 뒤 두 정렬된 배열을 합침 (분할 정복)항상 O(n log n), 안정O(n) 추가 메모리
퀵 정렬피벗을 골라 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누고 재귀평균적으로 가장 빠름, 제자리 정렬피벗이 계속 한쪽 끝이면 O(n²), 불안정
힙 정렬배열로 최대 힙을 만들고 루트(최댓값)를 끝으로 보내기를 반복항상 O(n log n), 추가 메모리 O(1)캐시 효율이 낮아 실제로는 퀵보다 느린 편, 불안정
void mergeSort(int[] a, int[] tmp, int lo, int hi) { // [lo, hi)
if (hi - lo < 2) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, tmp, lo, mid);
mergeSort(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo);
}

병합할 때 값이 같으면 왼쪽(a[i] <= a[j])을 먼저 넣기 때문에 원래 순서가 유지된다.

4. 퀵 정렬의 최악과 피벗 선택

피벗을 항상 첫 번째(또는 마지막) 원소로 고르면, 이미 정렬된 배열에서 매번 한쪽이 비어 분할이 n번 일어나 O(n²)이 된다. 그래서 실제 구현은 무작위 피벗이나 처음·중간·끝 중 중앙값(median-of-three)을 쓰고, 작은 구간에서는 삽입 정렬로 바꾸는 식으로 보완한다.

5. 안정 정렬이 왜 중요한가

안정 정렬은 정렬 기준이 같은 원소들의 원래 순서를 유지한다. 여러 기준으로 차례로 정렬할 때 의미가 생긴다.

정렬 전 (주문일 순): [A: 배송중, 5/1] [B: 완료, 5/2] [C: 배송중, 5/3]
상태로 안정 정렬: [A: 배송중, 5/1] [C: 배송중, 5/3] [B: 완료, 5/2]
→ 같은 상태 안에서는 주문일 순서가 그대로 남는다

불안정 정렬이면 A와 C의 순서가 바뀔 수 있다. 숫자 배열처럼 같은 값을 구분할 필요가 없으면 안정성은 상관없다.

6. 비교 정렬의 하한과 비비교 정렬

두 원소를 비교하는 방식으로만 정렬하면, 가능한 순열 n!개를 구분해야 하므로 최소 log₂(n!) ≈ n log n번 비교가 필요하다. 이보다 빠르려면 비교하지 않는 정렬을 써야 한다.

알고리즘방식조건
계수 정렬 (Counting)값마다 개수를 세어 누적합으로 위치 계산값의 범위 k가 작은 정수
기수 정렬 (Radix)자릿수별로 안정 정렬을 반복자릿수가 정해진 정수·문자열
버킷 정렬 (Bucket)구간별 버킷에 나눠 담고 각각 정렬값이 고르게 분포

7. 언어 내장 정렬

API알고리즘안정
Java Arrays.sort(int[] 등 기본형)Dual-Pivot QuicksortX (기본형이라 구분 불필요)
Java Arrays.sort(Object[]), Collections.sort, List.sortTimSort (병합 + 삽입 기반)O
JavaScript Array.prototype.sort엔진 구현 (ES2019부터 명세상 안정 정렬 필수)O

자바스크립트 sort()는 비교 함수를 주지 않으면 문자열로 바꿔 비교한다. [10, 9, 1].sort()의 결과는 [1, 10, 9]다. 숫자는 sort((a, b) => a - b)로 정렬한다.

8. 실제로 어떻게 적용되나

  1. 정렬은 직접 구현하지 않는다: 실무에서는 내장 정렬에 Comparator만 정의한다. list.sort(Comparator.comparing(Order::getStatus).thenComparing(Order::getCreatedAt))처럼 여러 기준을 한 번에 지정하는 게 가장 명확하다.
  2. DB에서 정렬할지 앱에서 정렬할지: 페이지 단위로 잘라야 하면 DB의 ORDER BY로 정렬해야 한다. 앱에서 정렬하면 이미 잘린 결과만 정렬하게 된다.
  3. 상위 k개만 필요할 때: 전체를 정렬(O(n log n))하지 않고 크기 k짜리 힙(PriorityQueue)을 유지하면 O(n log k)로 끝난다.

9. 면접 질문으로 정리

  1. Q. 퀵 정렬의 평균과 최악 복잡도, 최악이 생기는 경우는? 평균 O(n log n), 최악 O(n²)이다. 피벗이 매번 최솟값이나 최댓값으로 골라져 분할이 한쪽으로 치우칠 때(예: 정렬된 배열에서 첫 원소를 피벗으로) 생긴다.
  2. Q. 병합 정렬과 퀵 정렬을 비교하면? 병합 정렬은 항상 O(n log n)이고 안정하지만 O(n) 추가 메모리가 필요하다. 퀵 정렬은 제자리 정렬이고 평균적으로 더 빠르지만 최악 O(n²)이고 불안정하다.
  3. Q. 안정 정렬이란? 정렬 기준이 같은 원소들의 기존 상대 순서를 유지하는 정렬이다. 병합·삽입·버블 정렬이 안정, 퀵·힙·선택 정렬은 불안정하다.
  4. Q. 자바는 기본형과 객체 배열에 왜 다른 정렬을 쓰나? 기본형은 같은 값을 구분할 필요가 없어 빠른 퀵 정렬 계열을 쓰고, 객체는 안정성이 필요해 TimSort를 쓴다.
  5. Q. O(n log n)보다 빠른 정렬이 가능한가? 비교 기반으로는 불가능하다. 값의 범위가 제한된 정수라면 계수 정렬이나 기수 정렬로 선형 시간에 가능하다.
Gunmo Lee
since 2021.07
정렬 알고리즘 비교 정리: 버블·선택·삽입·병합·퀵·힙 정렬과 안정 정렬 | GM 오락실