다음 C 언어로 구현한 arraySort 함수에서 재귀 호출 횟수의 최… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

다음 C 언어로 구현한 arraySort 함수에서 재귀 호출 횟수의 최댓값이 가장 큰 배열 arr의 입력내용은? (단, arraySort 함수의 최초 호출 시 low 변수와 high 변수는 배열 arr의 첫 번째와 마지막 데이터의 인덱스이다)
#define SWAP(x,y) {int temp = x; x = y; y = temp;}

int splitArray(int arr[], int low, int high) {
   int pi = (low + high)/2;
   SWAP(arr[pi], arr[high]);
   int pivot = arr[high];

   int i = low - 1;
   for(int j = low; j < high; j++) {
      if(arr[j] < pivot) {
         i++;
         SWAP(arr[i], arr[j]);
      }
   }
   SWAP(arr[high], arr[i + 1]);
   return i + 1;
}

void arraySort(int arr[], int low, int high) {
   if(low < high) {
      int pi = splitArray(arr, low, high);
      arraySort(arr, low, pi - 1);
      arraySort(arr, pi + 1, high);
   }
}

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

2, 4, 6, 8, 10, 5, 3, 7, 1, 9

3, 6, 2, 8, 5, 10, 7, 1, 9, 4

10, 9, 8, 7, 6, 5, 4, 3, 2, 1

재귀 호출 횟수가 가장 큰 입력은 2, 4, 6, 8, 10, 5, 3, 7, 1, 9이다.
splitArray는 가운데 원소를 피벗으로 쓴다. 이 입력은 매 분할마다 피벗이 구간의 최댓값이나 최솟값이 되어 한쪽 부분 배열이 비는 최악 분할이 반복되고, 재귀 깊이가 9까지 내려가 호출 수도 18회로 가장 많다.
이미 오름차순인 배열은 가운데 원소가 중앙값이라 균등 분할되어 재귀 깊이 3, 호출 12회다.
3, 6, 2, 8, 5, 10, 7, 1, 9, 4 역시 분할이 비교적 고르게 나뉘어 재귀 깊이 3, 호출 12회다.
내림차순 배열도 가운데 원소가 중앙값 부근이라 재귀 깊이 4, 호출 12회에 그친다.