2. Divide & Conquer Algorithm (6) Summary
Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그, Heee님의 블로그를 참고하였다.
정렬 알고리즘 총정리
정렬 알고리즘을 비교해 표로 나타내면 다음과 같다. 알고리즘 이름을 클릭하면 관련 포스트로 이동한다. 보통 시간복잡도는 Average-Case를 많이 사용한다.
| Algorithm | Stable | In-place | Best | Average | Worst |
|---|---|---|---|---|---|
| Insertion | O | O | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Bubble | O | O | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Selection | X | O | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Merge | O | X | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n\log_2n)$ |
| Quick | X | O | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n^2)$ |
| Heap | X | O | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n\log_2n)$ |
| Shell | O | O | $O(n)$ | $O(n^{1.5})$ | $O(n^2)$ |
| Counting | O | X | . | $O(n+k)$ | . |
| Radix | O | X | . | $d \times O(n)$ | . |
| Bucket | O | X | . | $O(n)$ | . |
- Insertion Sort : 배열의 모든 요소를 앞에서부터 차례대로, 이미 정렬된 (앞의) 배열부분과 비교하여 자신의 위치를 찾아 삽입하며 정렬을 완성하는 알고리즘
- Bubble Sort : 서로 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘. 여러 번의 회전을 통해 정렬이 이루어진다.
- Selection Sort : 최대값(혹은 최소값)을 찾은 뒤 맨 뒤(혹은 맨 앞)의 값과 교환하며 정렬하는 알고리즘. 여러 번의 회전을 통해 정렬이 이루어진다.
- Merge Sort : 데이터를 쪼갤 수 없을 때 까지 쪼갠 뒤, 둘씩 크기를 비교해 정렬하며 합치는 알고리즘
- Quick Sort : 리스트의 pivot을 선택한 뒤, pivot보다 작은 값과 큰 값으로 리스트를 둘로 분할하는 과정을 반복해 정렬하는 알고리즘
- Heap Sort : 모든 노드가 힙 속성(각 노드의 값이 자신의 자식노드 값보다 큰 이진트리)을 만족하도록 재귀적으로 트리 구조를 만들어 정렬을 완성
- Shell Sort : 주어진 배열의 일정 간격(gap)만큼의 요소들에 대해 삽입정렬을 반복 수행
- Counting Sort : 입력값의 빈도를 세어서 이를 결과리스트의 인덱스로 활용, 입력리스트의 요소값을 해당하는 결과리스트 인덱스 위치에 채워 넣는 방식으로 정렬을 완성
- Radix Sort : 입력값의 자릿수($d$) 각각에 대해 카운팅정렬을 적용해 카운팅정렬의 단점 보완, 예컨대 10진법으로 표현된 입력값에 래딕스정렬을 적용하면 $k$값이 9로 작아짐
- Bucket Sort : 데이터 개수만큼의 버킷을 두어 데이터를 나누고 버킷별로 정렬한 후 합쳐 정렬을 완성
Conclusion
-
단순하지만 비효율적인 방법 : Insertion, Bubble, Selection
-
복잡하지만 효율적인 방법 : Merge, Quick, Heap