Total
Search
안정성/제자리여부/시간복잡도 비교
1.
안정성
•
값이 동일한 경우 상대적인 순서를 유지해야 안정임
•
안정성을 보장하는 알고리즘
◦
버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 카운팅 정렬, 버킷 정렬
2.
제자리 여부
•
제자리 정렬은 추가 메모리 사용 없이 입력 배열을 수정하며 정렬
•
제자리가 아닌 알고리즘: 병합 정렬, 기수 정렬, 카운팅 정렬, 버킷 정렬
3.
시간복잡도
•
O(n^2): 버블 정렬, 삽입 정렬, 선택 정렬 (비효율적)
•
O(nlogn) : 퀵 정렬, 병합 정렬, 힙 정렬 (효율적)
•
특수 상황에서 효율적인 정렬:
◦
O(nk): 기수 정렬 (k는 자리수 또는 범위)
◦
O(n+k): 카운팅 정렬 (k는 범위)
알고리즘 | 안정성 | 제자리 여부 | 최선 시간복잡도 | 평균 시간복잡도 | 최악 시간복잡도 |
선택 정렬 | 안정적이지 않음 | 제자리 | O(n^2) | O(n^2) | O(n^2) |
버블 정렬 | 안정적 | 제자리 | O(n) | O(n^2) | O(n^2) |
삽입 정렬 | 안정적 | 제자리 | O(n) | O(n^2) | O(n^2) |
셸 정렬 | 안정적이지 않음 | 제자리 | O(nlogn) | O(n^{1.25}) | O(n^2) |
퀵 정렬 | 안정적이지 않음 | 제자리 | O(nlogn) | O(nlogn) | O(n^2) |
병합 정렬 | 안정적 | 제자리 아님 | O(nlogn) | O(nlogn) | O(nlogn) |
힙 정렬 | 안정적이지 않음 | 제자리 | O(nlogn) | O(nlogn) | O(nlogn) |
카운팅(계수) 정렬 | 안정적 | 제자리 아님 | O(n+k) | O(n+k) | O(n+k) |
기수 정렬 | 안정적 | 제자리 아님 | O(nk) | O(nk) | O(nk) |
버킷 정렬 | 안정적 | 제자리 아님 | O(n) | O(n+k⋅log(k)) | O(n^2) |
요약
•
작은 데이터
◦
삽입 정렬 또는 버블 정렬
•
큰 데이터
◦
메모리 아껴야 하면 → 힙 정렬
◦
안정성이 중요하면 → 병합 정렬
◦
일반적으로 가장 빠름 → 퀵 정렬
•
특정 데이터 범위
◦
기수 정렬, 카운팅 정렬