정렬이란?
순서 없이 나열된 자료들을 특정한 키값에 따라 오름차순이나 내림차순으로 자료를 재배열하는 것을 의미한다.
정렬은 효율적인 자료 탐색을 위해서는 필수적이다.
정렬 알고리즘 분류
1. 비교 정렬
원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘
2. 안정 정렬 (Stable sort)
동일한 값에 대해 기존의 순서가 유지되는 정렬
3. 불안정 정렬 (Unstable sort)
동일한 값에 대해 기존의 순서가 바뀔 수 있는 정렬
4. 내부 정렬 (Internal sort)
정렬하고자 하는 모든 데이터가 메모리에 올라온 상태에서 정렬하는 방식
5. 외부 정렬 (External sort)
정렬하고자 하는 데이터의 크기가 커서 일부만 메모리에 올려놓은 상태에서 정렬을 수행하고, 정렬된 것을 다시 합치는 방식
6. 제자리 정렬 (In-place sort)
주어진 공간 외에 추가적인 공간을 사용하지 않는 정렬
정렬 알고리즘 비교
| 정렬 알고리즘 | 최선 | 평균 | 최악 | 분류 | 공간 |
|---|---|---|---|---|---|
| 버블 정렬 | O(N) | O(N^2) | O(N^2) | 안정, 비교 | O(N) |
| 선택 정렬 | O(N^2) | O(N^2) | O(N^2) | 불안정, 비교 | O(N) |
| 삽입 정렬 | O(N) | O(N^2) | O(N^2) | 안정, 비교 | O(N) |
| 퀵 정렬 | O(n log n) | O(n log n) | O(N^2) | 불안정, 비교 | O(log n) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | 안정, 비교 | O(N) |
[참고]
