[정보처리기사 실기] 정렬 알고리즘

Question

다음 정렬 알고리즘들의 최악 시간 복잡도를 비교했을 때, O(n log n)을 보장하는 알고리즘을 모두 쓰시오. - 힙 정렬 - 삽입 정렬 - 병합 정렬 - 셸 정렬

Accepted Answer

힙 정렬, 병합 정렬 — 힙 정렬과 병합 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다. 삽입 정렬은 최악 시간 복잡도가 O(n²)이고, 셸 정렬은 사용하는 간격 수열에 따라 다르지만 일반적으로 O(n²)이다.

정보처리기사 실기 정렬 알고리즘 기출문제 #2829