① 파이썬 전체 코드
② 실행 결과
출력은 예제 입력을 기준으로 작성했습니다. 실제 파이썬 실행은 IDLE에서 가능합니다.
공통 입력
[8, 3, 5, 1, 9, 2, 7, 4]
정렬 결과
[1, 2, 3, 4, 5, 7, 8, 9]
③ 알고리즘 비교표
| 알고리즘 | 시간 복잡도 | 추가 공간 |
|---|---|---|
| 버블 정렬 | O(n²) | O(1) |
| 선택 정렬 | O(n²) | O(1) |
| 삽입 정렬 | O(n²) | O(1) |
| 병합 정렬 | O(n log n) | O(n) |
| 퀵 정렬 | 평균 O(n log n), 최악 O(n²) | 평균 O(log n) |
| 힙 정렬 | O(n log n) | O(n) |
| 셸 정렬 | 간격에 따라 다름 | O(1) |
| 계수 정렬 | O(n+k) | O(n+k) |
| 기수 정렬 | O(d(n+b)) | O(n+b) |
| 파이썬 내장 정렬 | O(n log n) | O(n) |
시간 복잡도는 대표적인 최악 시간 기준이며, 퀵 정렬은 평균과 최악을 함께 표시했습니다. 힙 정렬의 코드 예시는 heapq를 사용하므로 추가 공간이 O(n)입니다. 셸 정렬은 간격 수열에 따라 달라집니다.