병합 정렬(Merge Sort)의 특징으로 올바른 것은?

쉬움 freeCodeCamp

보기 및 정답

A 배열을 절반씩 나눈 뒤 각각 정렬하고 병합하는 분할 정복 알고리즘으로, 항상 O(n log n) 시간 복잡도를 보장한다

B 배열 전체를 순회하면서 매 반복마다 현재 남은 요소들 중 최솟값을 찾아 앞쪽에 순서대로 배치한다

C 데이터가 반드시 정렬된 상태여야만 동작하는 탐색 전용 알고리즘으로, 정렬 기능은 지원하지 않는다

D 추가 메모리 공간을 전혀 사용하지 않고 배열 내부에서만 요소를 교환하는 대표적인 제자리(in-place) 정렬 알고리즘이다

병합 정렬은 배열을 반씩 나누어 재귀적으로 정렬한 후, 정렬된 두 배열을 합치는(merge) 방식입니다. 최선/최악 모두 O(n log n)을 보장하지만, 병합 시 O(n)의 추가 메모리가 필요합니다. 안정 정렬(stable sort)이라는 장점이 있습니다.

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

로그인