입력 : N개의 데이터
출력 : 정렬된 N개의 데이터
정렬 알고리즘의 중요요소
안정성(stability) - 같은 원소가 있을 때 원래 원소의 순서가 유지되는지 여부.
예를 들어 3, 2, 4, 2, 5를 정렬할 때를 생각해보자. 편의를 위해 원래 위치에 번호를 매겨보면,
3
|
2
|
4
|
2
|
5
|
1
|
2
|
3
|
4
|
5
|
이 된다.
만약 특정한 정렬 알고리즘이 안정성이 있는 정렬 알고리즘일 경우에는
2
|
2
|
3
|
4
|
5
|
2
|
4
|
3
|
1
|
5
|
만약 안정성이 없는 정렬 알고리즘일 경우에는
2
|
2
|
3
|
4
|
5
|
2
|
4
|
3
|
1
|
5
|
2
|
2
|
3
|
4
|
5
|
4
|
2
|
3
|
1
|
5
|
| 정렬 알고리즘 | 시간복잡도 | 안정성 |
| 선택 정렬(Selection Sort) | O(N^2) | X |
| 거품 정렬(Bubble Sort) | O(N^2) | O |
| 삽입 정렬(Insert Sort) | O(N^2) | O |
| 셸 정렬(Shell Sort) | O(N^2) | X |
| 합병 정렬(Merge Sort) | O(NlogN) | O |
| 힙 정렬(Heap Sort) | O(NlogN) | O |
| 퀵 정렬(Quick Sort) | O(N^2)*1 | X |
| 기수 정렬(Radix Sort) | O(N) | O |
댓글 없음:
댓글 쓰기