다음은 힙 정렬(heap sort) 알고리즘을 구현한 C 코드이다. 리… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지

다음은 힙 정렬(heap sort) 알고리즘을 구현한 C 코드이다. 리스트 L이 (61, 11, 59, 15, 48, 19)로 주어졌을 때, for 문에 관한 설명으로 옳은 것만을 모두 고르면? (단, 리스트 L을 배열로 표현할 때 색인 1부터 저장하고, n은 리스트의 크기를 나타낸다)
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

void heap_sort(int L[], int n){
    int i, temp;
    for(i = n/2; i >= 1; i--)  ······································ (가)
        adjust(L, i, n);
    for(i = n-1; i >= 1; i--) {  ·································· (나)
        SWAP(L[1], L[i+1], temp);
        adjust(L, 1, i);
    }
}

void adjust(int L[], int root, int n) {
    int next = 2 * root;
    int X = L[root];
    while(next <= n) {
        if(next < n && L[next] < L[next + 1])
            next++;
        if(X > L[next]) break;
        L[next / 2] = L[next];
        next *= 2;
    }
    L[next / 2] = X;
}
ㄱ. (가) for 문을 수행한 후 리스트 L에는 (61, 48, 59, 15, 19, 11)이 저장된다.
ㄴ. (나) for 문을 첫 1회 수행한 후 리스트 L에는 (59, 48, 19, 15, 11, 61)이 저장된다.
ㄷ. (나) for 문의 시간 복잡도는 $O(n\log n)$이다.

ㄱ, ㄴ

ㄱ, ㄷ

ㄴ, ㄷ

ㄱ, ㄴ, ㄷ

ㄱ은 틀리고 ㄴ과 ㄷ이 옳으므로 옳은 것은 ㄴ, ㄷ이다.
(가) 힙 구성: i=3에서 59와 자식 19 비교 → 그대로. i=2에서 11이 큰 자식 48(L[5])과 자리를 바꾼다. i=1에서 61이 두 자식보다 커서 그대로.
결과: (61, 48, 59, 15, 11, 19)
(나) 첫 회(i=5): L[1]과 L[6] 교환 → (19, 48, 59, 15, 11, 61)
adjust(L, 1, 5): 19가 큰 자식 59와 자리를 바꿈 → (59, 48, 19, 15, 11, 61)
ㄱ(틀림): 11은 큰 자식 48과 바뀌어 L[5]에 들어가므로 끝의 두 값은 11, 19 순서다.
ㄴ(옳음): 위 추적 결과와 같다.
ㄷ(옳음): (나) for 문은 약 n회 반복하고 매번 adjust가 힙 높이 $O(\log n)$만큼 내려가므로 $O(n\log n)$이다.