[자료구조 & 알고리즘] 정렬 알고리즘 총 정리

정렬 알고리즘 종류 및 비교

 

1. 비교 기반 정렬

1. 버블 정렬 (Bubble Sort)
2. 선택 정렬 (Selection Sort)
3. 삽입 정렬 (Insertion Sort)
4. 병합 정렬 (Merge Sort)
5. 퀵 정렬 (Quick Sort)
6. 힙 정렬 (Heap Sort)

---

2. 비교하지 않는 정렬

1. 계수 정렬 (Counting Sort)
2. 기수 정렬 (Radix Sort)
3. 버킷 정렬 (Bucket Sort)

 

알고리즘	최선	평균	최악	추가 메모리	안정성
버블 정렬	O(N)	O(N²)	O(N²)	O(1)	안정
선택 정렬	O(N²)	O(N²)	O(N²)	O(1)	불안정
삽입 정렬	O(N)	O(N²)	O(N²)	O(1)	안정
병합 정렬	O(N log N)	O(N log N)	O(N log N)	O(N)	안정
퀵 정렬	O(N log N)	O(N log N)	O(N²)	O(log N)	불안정
힙 정렬	O(N log N)	O(N log N)	O(N log N)	O(1)	불안정
계수 정렬	O(N + K)	O(N + K)	O(N + K)	O(K)	안정
기수 정렬	O(N × d)	O(N × d)	O(N × d)	O(N + K)	안정
버킷 정렬	O(N + K)	O(N + K)	O(N²)	O(N + K)	안정

 

---

1. 비교 기반 정렬 (Comparison-Based Sorting)

1.1 버블 정렬 (Bubble Sort)

• 작동 방식: 인접한 두 데이터를 비교하여 큰 값을 뒤로 보내는 방식.
• 시간 복잡도:
  • 최악/평균: O(N²)
  • 최선: O(N) (이미 정렬된 경우)
• 특징: 단순하지만 느림.
• 장점: 구현이 간단함.
• 단점: 비효율적이며 대규모 데이터에 적합하지 않음.

 

---

1.2 선택 정렬 (Selection Sort)

• 작동 방식: 배열에서 가장 작은 데이터를 선택해 앞쪽에 정렬하는 방식.
• 시간 복잡도:
  • 모든 경우 O(N²)
• 특징: 단순하며 메모리 추가 사용이 없음.
• 장점: 데이터 이동 횟수가 적음.
• 단점: 대규모 데이터에 비효율적.

출처: https://miro.medium.com/v2/resize:fit:1400/1*5WXRN62ddiM_Gcf4GDdCZg.gif

---

1.3 삽입 정렬 (Insertion Sort)

• 작동 방식: 데이터가 삽입될 위치를 찾아 정렬된 배열에 삽입.
• 시간 복잡도:
  • 최악/평균: O(N²)
  • 최선: O(N) (이미 정렬된 경우)
• 특징: 정렬된 데이터에 적합.
• 장점: 적은 데이터에서 효율적.
• 단점: 대규모 데이터에 비효율적.

---

1.4 병합 정렬 (Merge Sort)

• 작동 방식: 배열을 반으로 나눈 뒤, 각각을 정렬하고 병합.
• 시간 복잡도: 모든 경우 O(N log N)
• 특징: 안정 정렬 (Stable Sort).
• 장점: 성능이 안정적이며 대규모 데이터 처리에 적합.
• 단점: 추가 메모리 사용이 큼(O(N)).

 

---

1.5 퀵 정렬 (Quick Sort)

• 작동 방식: 피벗을 기준으로 작은 값과 큰 값을 분리한 뒤 재귀적으로 정렬.
• 시간 복잡도:
  • 평균: O(N log N)
  • 최악: O(N²) (피벗이 잘못 선택된 경우)
• 특징: 비균형 분할 방지를 위한 랜덤 피벗 선택 가능.
• 장점: 추가 메모리 없이 빠르게 작동.
• 단점: 최악의 경우 성능 저하.

 

 

---

1.6 힙 정렬 (Heap Sort)

• 작동 방식: 데이터를 힙 구조로 정렬.
• 시간 복잡도: 모든 경우 O(N log N)
• 특징: 비교 기반 정렬.
• 장점: 추가 메모리 사용이 적음.
• 단점: 구현이 비교적 복잡하며 안정 정렬이 아님.

 

---

2. 비교하지 않는 정렬 (Non-Comparison Sorting)

2.1 계수 정렬 (Counting Sort)

• 작동 방식: 각 데이터의 개수를 세어 정렬.
• 시간 복잡도: O(N + K) (K는 최대값의 범위)
• 특징: 데이터의 크기 범위가 좁을 때 효율적.
• 장점: 매우 빠름.
• 단점: 데이터의 범위가 크면 비효율적.

---

2.2 기수 정렬 (Radix Sort)

• 작동 방식: 데이터를 자릿수 기준으로 정렬.
• 시간 복잡도: O(d × (N + K)) (d는 자릿수)
• 특징: 숫자 또는 문자열 정렬에 적합.
• 장점: 범위가 큰 데이터도 처리 가능.
• 단점: 안정적이지만 추가 메모리 사용이 큼.

---

2.3 버킷 정렬 (Bucket Sort)

• 작동 방식: 데이터를 여러 버킷으로 나누고 각 버킷을 정렬 후 병합.
• 시간 복잡도: 평균: O(N + K), 최악: O(N²)
• 특징: 균등하게 분포된 데이터에 적합.
• 장점: 빠르게 정렬 가능.
• 단점: 균등 분포가 아닌 경우 비효율적.

 

---

정렬 알고리즘 선택 기준

1. 데이터 크기:
   • 작은 데이터: 삽입 정렬, 선택 정렬.
   • 큰 데이터: 퀵 정렬, 병합 정렬, 힙 정렬.
2. 메모리 사용:
   • 제한된 메모리: 퀵 정렬, 힙 정렬.
   • 추가 메모리 가능: 병합 정렬, 계수 정렬.
3. 데이터의 분포:
   • 균등 분포: 버킷 정렬.
   • 특정 범위: 계수 정렬.
4. 데이터의 안정성 요구:
   • 안정 정렬 필요: 병합 정렬, 계수 정렬.
   • 안정성 불필요: 퀵 정렬, 힙 정렬.

 

시각 자료 출처: wikipedia