[자료구조&알고리즘] 정렬(Sort)

자료구조에서 **정렬(Sorting)**이란, **데이터를 일정한 순서(예: 오름차순, 내림차순)**로 재배열하는 과정.

정렬은 많은 알고리즘 문제의 기본 작업으로, 탐색, 데이터 분석, 최적화 등에 필수적

📌 정렬의 목적

데이터 검색 속도 향상 (예: 이진 탐색 가능)
시각화, 출력 등에서 보기 좋게 정리
중복 제거, 군집화 등 다양한 처리 전 단계로 사용

🔷 1. 버블 정렬 (Bubble Sort)

원리: 인접한 두 원소를 비교해서 큰 값을 뒤로 보내는 방식.
시간 복잡도: O(n²)
공간 복잡도: O(1)
안정성: ✅ 안정 정렬
특징:
- 구현이 매우 간단함
- 거의 정렬된 상태에서는 빠르게 끝남 (최선 O(n))
- 성능은 매우 낮아 실전에서는 거의 사용하지 않음
과정:
- 1회전: [5, 2, 4, 3, 1] → [2, 5, 4, 3, 1] → [2, 4, 5, 3, 1] → [2, 4, 3, 5, 1] → [2, 4, 3, 1, 5]
- 가장 큰 수 5가 맨 뒤로 감
- 이 과정을 n-1회 반복

🔷 2. 선택 정렬 (Selection Sort)

원리: 남은 데이터 중 가장 작은 값을 선택하여 맨 앞과 교환
시간 복잡도: O(n²)
공간 복잡도: O(1)
안정성: ❌ 불안정 정렬
특징:
- 비교 횟수는 고정 (항상 n(n-1)/2)
- 교환 횟수는 적음 (최대 n-1회)
- 구조가 단순하지만 느림
과정:
- 1단계: [5, 2, 4, 3, 1] → 가장 작은 값 1과 교환 → [1, 2, 4, 3, 5]
- 2단계: [2, 4, 3, 5] → 가장 작은 값 2 (자리 그대로)
- 3단계: [4, 3, 5] → 3과 4 교환 → [1, 2, 3, 4, 5]

🔷 3. 삽입 정렬 (Insertion Sort)

원리: 현재 값을 앞의 정렬된 부분과 비교하여 적절한 위치에 삽입
시간 복잡도: O(n²), 최선 O(n)
공간 복잡도: O(1)
안정성: ✅ 안정 정렬
특징:
- 거의 정렬된 자료에서 매우 빠름
- 작은 데이터셋에 효과적
- 실제 사람의 정렬 방식과 유사
과정:
- 시작: [5] (이미 정렬됨)
- 2 삽입: [2, 5]
- 4 삽입: [2, 4, 5]
- 3 삽입: [2, 3, 4, 5]
- 1 삽입: [1, 2, 3, 4, 5]

🔷 4. 병합 정렬 (Merge Sort)

원리: 분할 정복. 배열을 반씩 나누고, 정렬된 상태로 병합
시간 복잡도: O(n log n)
공간 복잡도: O(n) (추가 배열 필요)
안정성: ✅ 안정 정렬
특징:
- 항상 O(n log n)의 성능
- 재귀 구조 기반
- 추가 메모리가 필요한 것이 단점
과정:
- 분할: [5,2,4,3,1] → [5,2], [4,3,1] → [5],[2],[4],[3],[1]
- 병합: [2,5], [3,4], [1] → [2,5], [1,3,4] → [1,2,3,4,5]

🔷 5. 퀵 정렬 (Quick Sort)

원리: 피벗을 기준으로 좌우로 분할, 재귀적으로 정렬
시간 복잡도: 평균 O(n log n), 최악 O(n²)
공간 복잡도: O(log n) (재귀 깊이)
안정성: ❌ 불안정 정렬
특징:
- 평균적으로 가장 빠른 정렬 중 하나
- 피벗 선택이 중요 (중간값 전략, 랜덤화 등)
- 실무에서 가장 많이 사용됨
과정 (피벗=3):
- [5,2,4,3,1] → 왼쪽[2,1] | 피벗 3 | 오른쪽[5,4]
- 정렬:
  - 왼쪽: [1,2]
  - 오른쪽: [4,5]
- 최종: [1,2,3,4,5]

🔹 기본 구현 (First-element pivot)

arr = [5, 2, 4, 3, 1]
pivot = arr[0]  # 첫 번째 요소를 피벗으로 선택

장점: 구현이 간단함
단점: 데이터가 이미 정렬된 상태일 경우 최악의 성능 (O(n²)) 발생 가능

🔹다른 피벗 선택 방법들

마지막 원소 사용
- pivot = arr[-1]
- 구현 간단하지만 위와 동일한 단점
중간 값 사용 (Middle element)
- pivot = arr[len(arr)//2]
- 성능이 비교적 안정적임
무작위 선택 (Random Pivot)
- pivot = random.choice(arr)
- 퀵 정렬의 평균 성능을 보장하기 위해 많이 쓰임
Median-of-three (삼요소 중앙값)
- pivot = median(arr[0], arr[mid], arr[-1])
- 분할 균형을 더 잘 잡아줘서 성능 안정적

퀵 정렬에서 "중간 값을 사용한다"는 말은 일반적으로 리스트의 중앙 위치(index 기준)의 요소를 피벗으로 선택한다는 의미

예를 들어:

arr = [5, 2, 4, 3, 1]
mid_index = len(arr) // 2  # 중앙 인덱스
pivot = arr[mid_index]     # 중앙 위치의 값, 여기선 4

📌 중간값과 중앙값의 차이

여기서 주의할 점은:

중간 위치의 값: 배열의 중간 인덱스에 있는 값
중앙값(통계에서의 median): 정렬된 배열에서 중앙에 있는 값 (진짜 중앙값)

예시:

arr = [100, 1, 3]
- 중간 위치 값: arr[1] → 1
- 중앙값: 정렬하면 [1, 3, 100] → 중앙값은 3

즉,

중간 위치 값: 간단하고 빠르지만 데이터 분포를 고려하지 않음
중앙값(통계적 median): 분포를 반영하지만 구하려면 정렬이 필요 → 성능 저하

실제 구현에서는 **"중간 위치의 값"**을 쓰는 게 일반적이고,
성능을 더 높이고 싶을 땐 "삼요소 중앙값 (median-of-three)" 기법을 사용해서 아래 세 요소 중 중앙값을 피벗으로 선택해:

첫 번째 값
중간 위치 값
마지막 값

🔷 6. 힙 정렬 (Heap Sort)

힙(Heap): 완전 이진 트리 형태의 우선순위 큐 자료구조
- 최대 힙: 부모 노드 ≥ 자식 노드
- 최소 힙: 부모 노드 ≤ 자식 노드
힙 정렬은 배열을 최대 힙으로 만든 뒤, 루트(최댓값)를 맨 끝으로 보내며 정렬하는 방식

원리: 힙 자료구조(이진 최대/최소 힙)를 이용하여 정렬
시간 복잡도: O(n log n)
공간 복잡도: O(1)
안정성: ❌ 불안정 정렬
특징:
- 메모리 효율적 (제자리 정렬)
- 병합 정렬보다 느릴 수 있음
- 우선순위 큐 구현 기반
과정:

🔷 7. 기수 정렬 (Radix Sort)

원리: 자릿수 기준으로 정렬을 여러 번 수행 (LSB부터)
시간 복잡도: O(nk) (k는 자릿수)
공간 복잡도: O(n + k)
안정성: ✅ 안정 정렬
특징:
- 비교 기반 아님
- 숫자, 문자열에 적합
- 정해진 범위가 있을 때 효율적 (예: 학번, 전화번호)
- 별도의 메모리 추가 필요

과정:
- [170, 45, 75, 90, 802, 24, 2, 66]
  
  🔹일의 자리 기준정렬
  0: [170, 90]
  2: [802, 2]
  4: [24]
  5: [45, 75]
  6: [66]
  [170, 90, 802, 2, 24, 45, 75, 66]
  
  🔹십의 자리 기준정렬
  0: [802, 2]
  2: [24]
  4: [45]
  6: [66]
  7: [170, 75]
  9: [90]
  [802, 2, 24, 45, 66, 170, 75, 90]
  
  🔹 백의 자리 기준 정렬
  0: [2, 24, 45, 66, 75, 90]
  1: [170]
  8: [802]
  [2, 24, 45, 66, 75, 90, 170, 802]

🔷 8. 2원 합병 정렬 (2-way Merge Sort)

원리: 일반 병합 정렬. 두 개의 정렬된 배열을 병합
시간 복잡도: O(n log n)
공간 복잡도: O(n)
안정성: ✅ 안정 정렬
특징:
- 병합 정렬과 동일
- 주로 외부 정렬(external sort)에 사용
과정:
- [5,2,4,3,1] → [5,2],[4,3,1] → [2,5],[1,3,4] → 병합 → [1,2,3,4,5]

🔷 9. 쉘 정렬 (Shell Sort)

원리: 특정 간격(gap)만큼 떨어진 요소끼리 삽입 정렬
시간 복잡도: 평균 O(n^1.5), 최악 O(n²), 일부 gap 전략 시 O(n log² n)
공간 복잡도: O(1)
안정성: ❌ 불안정 정렬
특징:
- 삽입 정렬보다 빠름
- 제자리 정렬, 구현 간단
- 성능은 gap 수열에 크게 의존

과정:
- 1. 초기 큰 gap으로 먼 거리 요소들 정렬
  2. 점차 gap을 줄여가며 세밀하게 정렬
  3. 마지막엔 gap = 1 → 삽입 정렬처럼 마무리
    
    📘 1단계: gap = 4
    - (0, 4): 8 ↔ 6
    - (1, 5): 5 ↔ 2
    - (2, 6): 3 ↔ 4
    - (3, 7): 7 ↔ 1
    → 각 그룹에서 삽입 정렬
    
    📘 2단계: gap = 2
    - (0, 2, 4, 6): 6, 3, 8, 4 → 삽입 정렬 → [3, 4, 6, 8]
    - (1, 3, 5, 7): 2, 1, 5, 7 → 삽입 정렬 → [1, 2, 5, 7]
    → 전체 배열:
    [3, 1, 4, 2, 6, 5, 8, 7]
    
    📘 3단계: gap = 1
    → [1, 2, 3, 4, 5, 6, 7, 8]
    → 정렬 완료
    🧠 요약
    초기 큰 gap으로 먼 거리 요소들 정렬
    점차 gap을 줄여가며 세밀하게 정렬
    마지막엔 gap = 1 → 삽입 정렬처럼 마무리

🔍 요약정리

알고리즘	시간 복잡도	공간 복잡도	안정성	특징
버블 정렬 (Bubble Sort)	O(n²)	O(1)	✅	간단하지만 비효율적
선택 정렬 (Selection Sort)	O(n²)	O(1)	❌	가장 작은 값을 선택해서 앞으로 이동
삽입 정렬 (Insertion Sort)	O(n²)	O(1)	✅	거의 정렬된 상태일 땐 빠름
병합 정렬 (Merge Sort)	O(n log n)	O(n)	✅	분할 정복 방식, 안정적
퀵 정렬 (Quick Sort)	평균 O(n log n), 최악 O(n²)	O(log n)	❌	분할 정복 방식, 매우 빠름
힙 정렬 (Heap Sort)	O(n log n)	O(1)	❌	힙 자료구조 사용
기수 정렬 (Radix Sort)	O(nk)	O(n + k)	✅	숫자나 문자열 정렬에 유리 (비교 기반 아님)
2원 합병 정렬	O(n log n)	O(n)	✅	분할 정복, 재귀 기반
쉘 정렬	평균 O(n^1.5), 최악 O(n²)	O(1)	❌	간격 기반 삽입 정렬

✅ 정렬 알고리즘 분류

비교 기반: 두 값 비교로 정렬 결정
(예: 버블, 삽입, 퀵, 병합, 힙)
비비교 기반: 비교 없이 자리 계산
(예: 계수 정렬, 기수 정렬)

📈 정렬 알고리즘 선택 기준

데이터 크기 (작은 배열: 삽입정렬 OK)
데이터의 정렬 상태 (거의 정렬: 삽입정렬 유리)
안정성 필요 여부 (같은 값 순서 유지 여부)
추가 메모리 사용 가능성

'자료구조&알고리즘' 카테고리의 다른 글

[자료구조&알고리즘] 최소비용신장트리(Prim, Kruskal, Dijkstra 알고리즘) (1)	2025.05.25
[자료구조&알고리즘] 트리(Tree) (0)	2025.05.24
[자료구조&알고리즘] 탐색(Search) (1)	2025.05.23

🔷 1. 버블 정렬 (Bubble Sort)

🔷 2. 선택 정렬 (Selection Sort)

🔷 3. 삽입 정렬 (Insertion Sort)

🔷 4. 병합 정렬 (Merge Sort)

🔷 5. 퀵 정렬 (Quick Sort)

📌 중간값과 중앙값의 차이

🔷 6. 힙 정렬 (Heap Sort)

🔷 7. 기수 정렬 (Radix Sort)

🔷 8. 2원 합병 정렬 (2-way Merge Sort)

🔷 9. 쉘 정렬 (Shell Sort)

🔍 요약정리

'자료구조&알고리즘' 카테고리의 다른 글

티스토리툴바