다음 C 코드는 쉘 정렬을 구현한 것이다. 코드의 출력 결과는?#inc… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

다음 C 코드는 쉘 정렬을 구현한 것이다. 코드의 출력 결과는?
#include <stdio.h>
void sort(int arr[], int n) {
  int count = 1;
  int i, j, k, h, val;
  for (h = n/2; h > 0; h /= 2) {
    for (i = 0; i < h; i++)  {
      for (j = i+h; j < n; j += h) {
        val = arr[j];
        k = j;
        while (k > h-1 && arr[k-h] > val) {
          arr[k] = arr[k-h];
          k -= h;
        }
        arr[k] = val;

        if (count == 5)
          for (int t = 0; t < 6; t++)
            printf("%d ", arr[t]);
        count++;
      }
    }
  }
}

int main() {
    int a[6] = {5, 9, 2, 3, 6, 7};
    sort(a, 6);
}

2 3 5 6 9 7

2 3 6 5 9 7

3 6 2 5 9 7

3 9 2 5 6 7

count가 5일 때 출력되는 배열은 2 3 6 5 9 7이다.
간격 h=3: 5·3 정렬로 3 9 2 5 6 7(count 1), 9·6 정렬로 3 6 2 5 9 7(count 2), 2·7은 그대로(count 3).
간격 h=1: 6 삽입은 이동 없음(count 4), 2 삽입은 맨 앞까지 이동해 2 3 6 5 9 7(count 5)이 되어 이때 출력한다.
2 3 5 6 9 7: 5까지 삽입한 count 6 이후의 상태다.
3 6 2 5 9 7: 간격 3 단계가 끝난 count 3·4 시점의 상태다.
3 9 2 5 6 7: count 1 직후의 상태다.