정답
gap의 변화: 4 → 2 → 1 → 0, ㉠의 실행 횟수는 2회, data[0]=12이고 data[6]=26이다.
출제 의도
이 문제는 셸 정렬(Shell sort)의 동작 원리를 이해하고, 주어진 C 코드에서 gap 변화 과정과 내부 반복문의 실행 흐름을 추적하며, 조건에 따라 break 문이 실행되는 횟수와 중간 출력 결과를 정확히 계산할 수 있는지를 평가한다.
풀이 과정
함수 호출은 shell_sort(data, 8)이며, 배열의 크기 cnt는 8이다. 바깥 반복문에서 gap은 cnt/2부터 시작하여 절반씩 감소한다.
$$ gap = \frac{8}{2} = 4 \rightarrow 2 \rightarrow 1 \rightarrow 0 $$
따라서 gap의 변화 순서는 4 → 2 → 1 → 0이다.
이제 gap = 4일 때를 추적한다. 초기 배열은
$$ [17, 25, 26, 18, 12, 33, 9, 35] $$
i는 4부터 7까지 반복된다.
i = 4일 때, k = 0에서 data[0]=17, data[4]=12이므로 조건 data[k] > data[k+gap]이 참이 되어 swap이 수행된다. break는 실행되지 않는다.
i = 5일 때, k = 1에서 data[1]=25, data[5]=33이므로 조건이 거짓이 되어 else로 진입하며 ㉠의 break가 실행된다. (1회)
i = 6일 때, k = 2에서 data[2]=26, data[6]=9이므로 swap이 수행되고 break는 실행되지 않는다.
i = 7일 때, k = 3에서 data[3]=18, data[7]=35이므로 조건이 거짓이 되어 break가 실행된다. (2회)
따라서 gap이 4일 때 ㉠의 break 실행 횟수는 총 2회이다.
gap = 4 단계가 끝난 후 배열은
$$ [12, 25, 9, 18, 17, 33, 26, 35] $$
이다. 이때 출력문(㉡)에 의해 출력되는 배열에서 data[0]과 data[6]의 값은 각각 12와 26이다.