[7급 국가직 자료구조론 2025년 9번]

다음은 힙 정렬(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 문의 시간 복잡도는 $\mathrm{O}(n\log n)$이다.