[자료구조] 퀵소트, 머지소트, 버블소트, 팀소트

다양한 정렬의 방식

대표적인 정렬의 방식은 여러가지가 있습니다.

대부분의 언어에서 기본 문법에 편입된 정렬 방식은

토대가 되는 여러 정렬 방식의 장점만을 모아 만든 하이브리드 알고리즘을 쓰게 되는데,

이 토대가 되는 알고리즘은 대표적으로 퀵소트(Quick Sort)와 머지소트(Merge Sort, 병합정렬), 그리고 삽입 정렬이 있을 것 같습니다!

C에서는 퀵소트를, C++에서는 Quick과 Heap을 합친 Introsort를 사용하며,

파이썬의 sort(), sorted 메서드나 자바의 arrayList에서 사용하는 정렬은 병합 정렬과 삽입 정렬의 하이브리드 정렬 방식인 Tim sort를 사용합니다!

먼저, 토대가 되는 세 기본 정렬 알고리즘 비교표를 보도록 하겠습니다.

퀵소트, 머지소트, 삽입 정렬 비교표

기준	퀵소트 (Quick Sort)	머지소트 (Merge Sort)	삽입 정렬 (Insertion Sort)
동작 방식	분할 정복, 피벗 기준 정렬	분할 정복, 반으로 나눠 병합	앞에서부터 정렬된 위치 삽입
시간 복잡도 (최선)	O(n log n)	O(n log n)	O(n)
시간 복잡도 (평균)	O(n log n)	O(n log n)	O(n²)
시간 복잡도 (최악)	O(n²) (편향된 피벗 선택)	O(n log n)	O(n²)
공간 복잡도	O(log n) (제자리)	O(n) (추가 배열 필요)	O(1) (제자리)
안정성	불안정 (원소 순서 변경 가능)	안정적 (원소 순서 유지)	안정적 (원소 순서 유지)
데이터 크기 적합성	큰 데이터 (일반적인 경우)	대규모 데이터, 외부 정렬	작은 데이터, 부분 정렬
재귀적 동작 여부	재귀적, 분할 기반	재귀적, 병합 기반	비재귀적 가능, 순차 탐색
사용 사례	표준 라이브러리(C, C++, Java)	대규모 데이터 정렬(Python)	작은 배열 최적화(Timsort)
특징 요약	평균 성능이 매우 빠름	안정적, 최악 성능 보장	간단, 작은 데이터 최적화

• 퀵소트(Quick Sort): 평균 성능이 매우 뛰어나며, 제자리 정렬이 가능해 메모리 효율적입니다. 다만 최악의 경우 O(n²) 성능이 발생할 수 있어 주의해야 합니다.

• 머지소트(Merge Sort): 안정적 정렬(Stable Sort)이며, 항상 O(n log n) 성능을 보장합니다. 추가 메모리가 필요하므로 대규모 데이터에 적합합니다.

• 삽입 정렬(Insertion Sort): 소규모 데이터나 부분적으로 정렬된 데이터에서 빠릅니다. 단순한 구조로 학습 목적이나 특정 하이브리드 정렬에 최적화 방식으로 사용됩니다.

• 안정적 정렬이란, 값이 같은 원소들의 순서가 정렬 전과 후에도 유지되는 특성으로, 원소의 기존 순서 유지가 필요한 다중 필드 정렬 작업에서 유용합니다!

퀵소트?

• 분할 정복(Divide and Conquer) 알고리즘

• 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분한

• 재귀적으로 좌우 리스트를 정렬 후 병합

• 평균 성능이 매우 우수하여, 대부분의 경우 O(n log n)을 유지하며, 추가 메모리가 필요 없는 제자리 정렬이 가능합니다.

• 다만 매번 최악의 피벗을 선택할 시, O(n^2)의 결과가 나올 수 있으며, 불안정 정렬입니다.

정렬 순서

리스트: [8, 3, 7, 6, 2]
피벗 선택: 8 (첫 번째 요소)

정렬 후: [3, 7, 6, 2] + [8] + []
-------------------------------
왼쪽 리스트 재귀 호출

리스트: [3, 7, 6, 2]
피벗 선택: 3 (첫 번째 요소)

정렬 후: [2] + [3] + [7, 6]
-------------------------------
오른쪽 리스트 재귀 호출

리스트: [7, 6]
피벗 선택: 7 (첫 번째 요소)

정렬 후: [6] + [7]
-------------------------------
최종 병합

[2] + [3] + [6, 7] + [8]

→ [2, 3, 6, 7, 8]

머지 소트?

• 퀵소트와 마찬가지로, 분할 정복 방식

• 리스트를 반으로 나누고, 각각 정렬 후 병합합니다.

• 항상 O(n log n)이란 높은 성능을 보장하며, 안정적 정렬 방식입니다.

• 다만 리스트를 말 그대로 쪼개기 때문에 추가적인 메모리가 필요합니다.

정렬 순서

1. 리스트 분할

리스트: [8, 3, 7, 6, 2]

왼쪽: [8, 3, 7]
오른쪽: [6, 2]

2. 왼쪽 리스트 재귀 분할

왼쪽: [8] (단일 요소)
오른쪽: [3, 7]

2-1. 오른쪽 [3, 7] 재귀 분할:

왼쪽: [3]
오른쪽: [7]

3. 오른쪽 리스트 재귀 분할

왼쪽: [6]
오른쪽: [2]

4. 정렬 리스트 병합

병합 [3] + [7] → [3, 7]
병합 [8] + [3, 7] → [3, 7, 8]
병합 [6] + [2] → [2, 6]

5. 최종 병합

왼쪽 리스트: [3, 7, 8]
오른쪽 리스트: [2, 6]

[2] → [3] → [6] → [7] → [8]

삽입 정렬

• 왼쪽부터 시작해서 정렬된 부분과 비교하며 적절한 위치에 요소를 삽입하는 방식

• 작은 요소부터 오른쪽으로 확장하며 정렬을 완료합니다.

• 제자리 정렬이라 공간 복잡도가 O(1)로, 안정적 정렬이며 추가 메모리가 필요없다는 장점이 있습니다.

• 다만 평균적인 시간 복잡도를 O(n^2)을 상정해야 하므로, 대규모 데이터에서는 성능 저하가 매우 심합니다.

• 그렇기 때문에 실제로는 Timsort, introsort 등의 하이브리드 알고리즘의 일부로 사용됩니다.

리스트 초기 상태: [8, 3, 7, 6, 2]

1단계: 요소 `3` 삽입 → [3, 8, 7, 6, 2]
2단계: 요소 `7` 삽입 → [3, 7, 8, 6, 2]
3단계: 요소 `6` 삽입 → [3, 6, 7, 8, 2]
4단계: 요소 `2` 삽입 → [2, 3, 6, 7, 8]  ← 정렬 완료

팀 소트 (Tim sort)

• Timsort