알고리즘에서 '힙(Heap)' 자료구조의 '힙 정렬(Heap Sort)' 시간 복잡도와 특징으로 올바른 것은?

Q: 알고리즘에서 '힙(Heap)' 자료구조의 '힙 정렬(Heap Sort)' 시간 복잡도와 특징으로 올바른 것은?

최선, 평균, 최악 모두 O(n log n)이며, 추가 메모리 공간이 O(1)인 제자리 정렬이다 힙 정렬은 최대 힙(또는 최소 힙)을 구성한 후 루트를 꺼내어 정렬합니다. 모든 경우에 O(n log n)이 보장되며, 별도 배열 없이 제자리(in-place)에서 정렬합니다. 단, 동일한 값의 상대적 순서가 보존되지 않아 불안정 정렬(Unstable Sort)입니다.

쉬움 freeCodeCamp

보기 및 정답

A 최선, 평균, 최악 모두 O(n log n)이며, 추가 메모리 공간이 O(1)인 제자리 정렬이다

B 평균 시간 복잡도는 O(n log n)이지만 최악의 경우에는 O(n²)으로 성능이 크게 저하될 수 있다

C O(n)의 시간 복잡도를 가지며, 비교 기반 정렬 중에서 가장 빠른 성능을 보장한다

D 동일한 키 값을 가진 요소들의 원래 순서가 정렬 후에도 유지되는 안정 정렬이다

해설

힙 정렬은 최대 힙(또는 최소 힙)을 구성한 후 루트를 꺼내어 정렬합니다. 모든 경우에 O(n log n)이 보장되며, 별도 배열 없이 제자리(in-place)에서 정렬합니다. 단, 동일한 값의 상대적 순서가 보존되지 않아 불안정 정렬(Unstable Sort)입니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

로그인

추가 정보 입력

회원가입

비밀번호 찾기

알고리즘에서 '힙(Heap)' 자료구조의 '힙 정렬(Heap Sort)' 시간 복잡도와 특징으로 올바른 것은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

모두를 위한 진짜 쎈 바이브코딩