한국어
메뉴

자료 구조와 알고리즘

최악의 경우에도 시간 복잡도가 O(n log n)이고, 작업용 배열 등의 추가 기억 영역을 거의 사용하지 않고 정렬할 수 있는 정렬 방식은?

  1. A병합 정렬
  2. B힙 정렬
  3. C퀵 정렬
정답과 해설 보기

정답: B. 힙 정렬

힙 정렬은 배열 안에 이진 힙을 만들고, 루트의 최댓값을 맨 끝과 교환하여 힙을 줄이는 것을 반복하므로 최악에도 O(n log n)이며, 추가 영역은 상수로 충분합니다. 병합 정렬도 최악 O(n log n)이지만, 배열로 수행하려면 작업용으로 n에 비례하는 영역이 필요합니다. 퀵 정렬은 평균 O(n log n)으로 실제로는 빠르지만, 피벗의 선택 방법과 데이터에 따라서는 O(n²)이 됩니다. 덧붙여 힙 정렬은 떨어진 위치의 원소를 비교하므로 캐시 효율이 나쁘고, 안정적이지도 않습니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. (이름, 점수) 데이터 (A, 80), (B, 70), (C, 80), (D, 70)이 이 순서로 늘어서 있다. 점수의 오름차순으로 안정 정렬했을 때 이름의 순서는?
  2. 퀵 정렬의 시간 복잡도가 O(n²)이 되는 전형적인 경우는?
  3. 병합 정렬에서 오름차순으로 정렬된 두 열 1, 4, 7, 9와 2, 3, 8, 10을, 맨 앞끼리 비교하여 작은 쪽을 출력하는 것을 반복하여 하나의 열로 합친다(병합한다). 한쪽 열이 비면 나머지는 비교하지 않고 그대로 출력한다. 비교 횟수는 몇 회인가?
  4. 이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
  5. 부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?