다음 C 언어로 구현한 sort 함수에서 (가) 문장이 수행되는 횟수가… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

다음 C 언어로 구현한 sort 함수에서 (가) 문장이 수행되는 횟수가 가장 작은 배열 arr의 입력내용은? (단, n ＝ 5이다)
void sort(int arr[], int n) {
   int i, key, j;
   for(i = 1; i < n; i++) {
      key = arr[i];
      j = i - 1;
      while(j >= 0 && arr[j] < key) {
         arr[j + 1] = arr[j]; ···········(가)
         j = j - 1;
      }
      arr[j + 1] = key;
   }
}

1, 2, 3, 4, 5

5, 3, 4, 7, 6

8, 3, 10, 7, 2

10, 9, 8, 7, 6

(가)가 가장 적게 수행되는 입력은 10, 9, 8, 7, 6이다.
조건이 arr[j] < key이므로 이 함수는 내림차순 삽입 정렬이고, (가)의 수행 횟수는 앞 원소가 뒤 원소보다 작은 쌍의 수와 같다.
1, 2, 3, 4, 5는 모든 쌍이 앞이 작아 10회로 최대다.
5, 3, 4, 7, 6은 (5,7)(5,6)(3,4)(3,7)(3,6)(4,7)(4,6)의 7회다.
8, 3, 10, 7, 2는 (8,10)(3,10)(3,7)의 3회다.
10, 9, 8, 7, 6은 이미 내림차순이라 0회다.