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

728x90

참고 포스트

C언어로 다양한 정렬 알고리즘을 활용하여 정수 오름차순 구현

2025.01.11 - [Computer Science/C 언어] - [C언어 22] 정렬 알고리즘 총 정리: C언어 구현

[C언어 22] 정렬 알고리즘 총 정리: C언어 구현

정렬 알고리즘은 데이터의 순서를 특정 기준(오름차순/내림차순)에 따라 배열하는 과정입니다. 백준 2751번 문제(정수 오름차순 정렬)을 활용하여 C 언어로 구현할 수 있는 다양한 정렬 알고리즘

rnasterofmysea.tistory.com

정렬 알고리즘의 핵심 개념

1️⃣ 비교 정렬과 비비교 정렬

비교 정렬 (Comparison Sort)

정의: 두 요소를 비교하여 자리를 바꾸는 방식으로 정렬.
특징:
- 입력 데이터의 값의 크기 비교가 필수.
- 시간 복잡도의 하한이 O(n log n).
예시 알고리즘:
- 퀵 정렬, 병합 정렬, 힙 정렬, 삽입 정렬, 선택 정렬.

비비교 정렬 (Non-Comparison Sort)

정의: 요소 간의 직접 비교 없이 키 값이나 다른 속성을 사용하여 정렬.
특징:
- 특정한 조건에서 O(n) 시간 복잡도를 가짐.
- 데이터가 정수 또는 제한된 범위에서 분포되어 있을 때 유리.
예시 알고리즘:
- 카운팅 정렬, 기수 정렬, 버킷 정렬.

2️⃣ 안정 정렬과 불안정 정렬

안정 정렬 (Stable Sort)

정의: 값이 같은 요소들의 상대적인 순서가 정렬 전과 동일하게 유지됨.
특징:
- 데이터의 기존 순서를 유지해야 하는 상황에서 중요.
- 예: 병합 정렬, 삽입 정렬, 버블 정렬.

불안정 정렬 (Unstable Sort)

정의: 값이 같은 요소들의 상대적인 순서가 변경될 수 있음.
특징:
- 상대적인 순서가 중요하지 않은 경우 사용.
- 예: 퀵 정렬, 힙 정렬, 선택 정렬.

3️⃣ 시간 복잡도

정렬 알고리즘의 효율성을 평가하는 주요 기준입니다.

알고리즘	최선의 경우	최악의 경우	평균
버블 정렬	O(n)	O(n²)	O(n²)
삽입 정렬	O(n)	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)	O(n²)
퀵 정렬	O(n log n)	O(n log n)	O(n²)
병합 정렬	O(n log n)	O(n log n)	O(n log n)
힙 정렬	O(n log n)	O(n log n)	O(n log n)
기수 정렬	O(nk)	O(nk)	O(nk)

n: 정렬할 요소의 개수.
k: 정렬 대상 숫자의 자릿수 (기수 정렬에서 사용).

4️⃣ 공간 복잡도

정렬 알고리즘이 사용하는 추가 메모리의 양입니다.

알고리즘	공간 복잡도	특징
버블 정렬	O(1)	제자리 정렬 (In-Place)
삽입 정렬	O(1)	제자리 정렬 (In-Place)
선택 정렬	O(1)	제자리 정렬 (In-Place)
퀵 정렬	O(log n)	재귀 호출로 인한 추가 메모리 필요
병합 정렬	O(n)	비제자리 정렬 (Not In-Place)
힙 정렬	O(1)	제자리 정렬 (In-Place)
기수 정렬	O(n + k)	비제자리 정렬 (Not In-Place)

각 정렬 알고리즘 원리 & 특징

1. 비교 기반 정렬

버블 정렬 (Bubble Sort)
선택 정렬 (Selection Sort)
삽입 정렬 (Insertion Sort)
병합 정렬 (Merge Sort)
퀵 정렬 (Quick Sort)
힙 정렬 (Heap Sort)

2. 비교하지 않는 정렬

계수 정렬 (Counting Sort)
기수 정렬 (Radix Sort)
버킷 정렬 (Bucket Sort)

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²)
특징: 균등하게 분포된 데이터에 적합.
장점: 빠르게 정렬 가능.
단점: 균등 분포가 아닌 경우 비효율적.

정렬 알고리즘 선택 기준

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

시각 자료 출처: wikipedia

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.