n개의 원소를 정렬하는 방법 중 평균 수행시간 복잡도와 최악 수행시간 … | [정보처리산업기사 필기] 20년 2회차 기출문제 상세 페이지

정렬 알고리즘의 시간 복잡도를 비교하면, 힙 정렬만이 평균과 최악 모두 O(n log₂ n)을 만족한다.
삽입 정렬: 평균 O(n²), 최악 O(n²)
버블 정렬: 평균 O(n²), 최악 O(n²)
선택 정렬: 평균 O(n²), 최악 O(n²)
힙 정렬은 최소 힙 또는 최대 힙 구조를 이용하여 원소를 재배열할 때 분할 정복 원리에 따라 일정하게 log n 깊이의 비교와 교환을 수행하므로, 데이터 배열 상태에 관계없이 항상 O(n log₂ n)의 성능을 보장한다.