정렬 알고리즘 종류
현재 많은 수의 알고리즘이 존재하지만 그중 실제 구현에서는 몇가지 알고리즘만 사용됩니다.
자바, C++ 등의 언어에서는 라이브러리로 O(n log n) 하한의 정렬 알고리즘을 제공하여 그냥 사용하면 되지만, 정렬 알고리즘을 더 깊게 공부하거나, 효율적인 정렬 알고리즘을 사용하려는 개발자를 위해 정렬 알고리즘에 대한 이해는 필수입니다.
실제 구현 시 사용되는 몇가지 알고리즘에 대해 비교 설명 해보겠습니다.
(각 알고리즘에 대한 상세 설명 및 구현방법은 생략합니다. 추후에 정리해서 올릴게요!)
비교 정렬 알고리즘 성능
이름 |
최적(Best) |
평균(Average) |
최악(Worst) |
메모리 |
안정성(Stable)* |
퀵(Quick) 정렬 |
n log n |
n log n |
n^2 |
log n ~ n |
No |
합병(Merge) 정렬 |
n log n |
n log n |
n log n |
n |
Yes |
삽입(Insertion) 정렬 |
n |
n^2 |
n^2 |
1 |
Yes |
힙(Heap) 정렬 | n log n | n log n | n log n | 1 | No |
Intro Sort |
n log n |
n log n |
n log n |
log n |
No |
선택(Selection) 정렬 |
n^2 |
n^2 |
n^2 |
1 |
No |
쉘(Shell) 정렬 |
n log n |
gap에 따라 다름 |
1 |
No |
|
거품(Bubble) 정렬 |
n |
n^2 |
n^2 |
1 |
Yes |
* Stable(안정성) : 같은 값에 대해 정렬 시도 후 위치가 바뀌지 않으면 Stable 하다고 하며, 위치가 서로 바뀔 수 있다면 Not Stable 하다고 합니다.
1. 퀵 정렬(Quick Sort)
- 분할 및 정복 알고리즘으로, 피벗이라는 요소를 사용하여 배열을 분할 합니다.
- 낮은 오버헤드로 다른 O(n log n) 정렬 알고리즘 보다 빠른 성능을 보입니다.
- 최악의 경우 성능이 O(n^2)입니다만, 드문 경우로써 피벗 요소를 잘 선택하여 O(n log n)의 성능을 얻을 수 있습니다.
2. 합병 정렬(Merge Sort)
- 비교 기반 분할 정복 정렬 알고리즘 입니다.
- Python과 Java의 표준 정렬 루틴에 사용되는 Timsort 알고리즘에 사용됩니다.
3. 힙 정렬(Heap Sort)
- 특별한 유형의 데이터 구조 이진트리를 생성하여 사용합니다.
- 퀵 정렬보다 대부분 다소 느리지만 최악의 경우 O(n log n)이라는 이점이 있습니다.
4. 삽입 정렬(Insertion Sort)
- 작은 데이터 셋(data set)에 널리 사용됩니다.
- 대부분 정렬 된 목록에 비교적 효율적이며, 더 복잡한 알고리즘의 일부로 사용되는 간단한 정렬 알고리즘입니다.
5. Intro Sort
- 하이브리드 정렬 알고리즘으로 퀵 정렬과 힙 정렬을 결합 하여 구현된 알고리즘입니다.
- C++ STL(표준 라이브러리)에서 제공합니다.
6. 쉘 정렬(Shell Sort)
- 적은 수의 코드와 합리적으로 빠르며, 임베디드 및 구형 메인 프레임 메모리에 사용됩니다.
7. 거품 정렬(Bubble Sort)
- 구현하기 가장 간단한 알고리즘이지만 O(n^2)으로 정렬 되지 않은 대형 데이터 셋에서 거의 사용되지 않습니다.
- 거의 정렬된 데이터에서 효율적으로 사용됩니다. O(n)
비 비교 정렬 알고리즘 성능
이름 | 최적(Best) | 평균(Average) | 최악(Worst) | 메모리 | 안정성(Stable) |
버킷(Bucket) 정렬 | - | n+k | (n^2) * k | 2^k | Yes |
계수(Counting) 정렬 | - | n+r | n+r | n+r | Yes |
기수(Radix) 정렬 | - | n * (k / d) | n * (k / d) | n+(2^d) | Yes |
1. 버킷 정렬(Bucket Sort)
- 배열을 유한 개수의 버킷으로 분할하여 계산하는 분할 정복 정렬 알고리즘입니다.
- 데이터 셋 요소가 모든 버킷에 고르게 분산될 때 가장 최적한 성능을 보입니다.
- 버킷을 할당하기 위한 메모리가 많이 필요합니다.
2. 계수 정렬(Counting Sort)
- 정수 정렬 알고리즘으로 정수 배열(리스트)에 한정적입니다.
- 숫자 크기(r)에 따라 매우 큰 영향을 받을 수 있으며 n에 비해 r이 매우 커지는 경우 비 효율적입니다.
3. 기수 정렬(Radix Sort)
- 자리수 d에 따라 공간 복잡도가 매우 커질 수 있습니다.
이상 정렬 알고리즘에 대해 비교 분석 해 보았습니다.
질문 또는 오타나 잘못된 정보가 있는 경우 댓글로 달아주세요!
공감♡ 버튼을 눌러주시면 더욱 유용하고 좋은 포스팅으로 찾아 뵙겠습니다.
'자료구조, 알고리즘' 카테고리의 다른 글
| [BOJ] 8979 올림픽 - 문제 풀이 (1) | 2019.03.29 |
|---|---|
| 검색 알고리즘 종류 (2) | 2018.09.11 |
| 자료구조 그래프(Graph) (1) | 2018.09.06 |
| 자료구조 힙(Heap) (0) | 2018.09.05 |
| 자료구조 이진 탐색 트리(Binary Search Tree) (0) | 2018.09.01 |
| 자료구조 트리(Tree) (0) | 2018.08.30 |
| [자료구조] 큐 QUEUE (0) | 2018.08.19 |
| [자료구조] 스택 STACK (0) | 2018.08.19 |
