2016. 11. 9. 23:52ㆍBasic/Data Structure
정렬 알고리즘의 성능 비교
알고리즘 | 최선 | 평균 | 최악 |
삽입 정렬 | O(n) | O(n^2) | O(n^2) |
선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
버블 정렬 | O(n^2) | O(n^2) | O(n^2) |
쉘 정렬 | O(n) | O(n^1.5) | O(n^1.5) |
퀵 정렬 | O(nlog 2n) | O(nlog 2n) | O(n^2) |
힙 정렬 | O(nlog 2n) | O(nlog 2n) | O(nlog 2n) |
합병 정렬 | O(nlog 2n) | O(nlog 2n) | O(nlog 2n) |
기수 정렬 | O(dn) | O(dn) | O(dn) |
- 최적의 정렬 방법은 정렬해야 할 데이터의 수, 크기, 타입에 따라 달라지므로 정렬 방법들의 장단점을 잘 이해하여 적합한 정렬을 사용할 수 있어야 합니다.
정렬 알고리즘별 실험 결과
- 정수 60000개 정렬
알고리즘 | 실행시간 (단위 : 초) |
삽입 정렬 | 7.438 |
선택 정렬 | 10.842 |
버블 정렬 | 22.894 |
쉘 정렬 | 0.056 |
힙 정렬 | 0.034 |
합병 정렬 | 0.026 |
퀵 정렬 | 0.014 |
- 삽입, 선택, 버블 정렬은 정렬속도가 느려서 비효율적입니다.
정렬 알고리즘별 안정성, 추가 메모리 필요 여부
알고리즘 | 안정성 | 추가 메모리 필요 |
삽입 정렬 | O | X |
선택 정렬 | X | X |
버블 정렬 | O | X |
쉘 정렬 | X | X |
힙 정렬 | X | X |
합병 정렬 | O | O |
퀵 정렬 | X | X |
기수 정렬 | O | O |
- 안정성 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬의 성능 비교
알고리즘 | 최선 | 평균 | 최악 |
삽입 정렬 | O(n) | O(n^2) | O(n^2) |
선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
버블 정렬 | O(n^2) | O(n^2) | O(n^2) |
쉘 정렬 | O(n) | O(n^1.5) | O(n^1.5) |
퀵 정렬 | O(nlog 2n) | O(nlog 2n) | O(n^2) |
힙 정렬 | O(nlog 2n) | O(nlog 2n) | O(nlog 2n) |
합병 정렬 | O(nlog 2n) | O(nlog 2n) | O(nlog 2n) |
기수 정렬 | O(dn) | O(dn) | O(dn) |
- 최적의 정렬 방법은 정렬해야 할 데이터의 수, 크기, 타입에 따라 달라지므로 정렬 방법들의 장단점을 잘 이해하여 적합한 정렬을 사용할 수 있어야 합니다.
정렬 알고리즘별 실험 결과
- 정수 60000개 정렬
알고리즘 | 실행시간 (단위 : 초) |
삽입 정렬 | 7.438 |
선택 정렬 | 10.842 |
버블 정렬 | 22.894 |
쉘 정렬 | 0.056 |
힙 정렬 | 0.034 |
합병 정렬 | 0.026 |
퀵 정렬 | 0.014 |
- 삽입, 선택, 버블 정렬은 정렬속도가 느려서 비효율적입니다.
정렬 알고리즘별 안정성, 추가 메모리 필요 여부
알고리즘 | 안정성 | 추가 메모리 필요 |
삽입 정렬 | O | X |
선택 정렬 | X | X |
버블 정렬 | O | X |
쉘 정렬 | X | X |
힙 정렬 | X | X |
합병 정렬 | O | O |
퀵 정렬 | X | X |
기수 정렬 | O | O |
- 안정성 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬
출처 : http://wonjayk.tistory.com/225
'Basic > Data Structure' 카테고리의 다른 글
| 배열(Array) (0) | 2016.11.09 |
|---|---|
| 연결리스트(Linked List) (0) | 2016.11.09 |
| 기수정렬 (Radix Sort) (0) | 2016.11.09 |
| 힙 정렬 (Heap Sort) (0) | 2016.11.09 |
| 퀵 정렬 (Quick Sort) (0) | 2016.11.09 |