문제
다음 정렬 알고리즘 중 최선 시간 복잡도가 O(n)인 것을 쓰시오.
- 삽입 정렬
- 힙 정렬
- 계수 정렬
- 쉘 정렬
정답
삽입 정렬, 계수 정렬
삽입 정렬, 계수 정렬삽입정렬, 계수정렬계수 정렬, 삽입 정렬계수정렬, 삽입정렬
해설
삽입 정렬은 이미 정렬된 배열에서 최선 시간 복잡도가 O(n)이다. 계수 정렬은 입력 범위가 제한적일 때 항상 O(n+k)로 선형 시간에 동작한다. 힙 정렬은 항상 O(n log n), 쉘 정렬은 최선의 경우에도 O(n log n)이다.