배열의 역로그를 계산하기 위해 병합 정렬 알고리즘을 사용하여 작성된 C/C++ 프로그램이 있습니까?

주어진 배열을 정렬하는 동안 발생하는 반전 횟수를 반전 횟수라고 합니다. 역 문제는 병합 정렬 알고리즘을 사용하여 풀 수 있는 고전적인 문제입니다. 이 문제 v에서는 왼쪽에 있는 요소 중 그보다 큰 모든 요소의 수를 계산하고 그 수를 출력에 추가합니다. 이 논리는 병합 정렬의 병합 기능에서 완성됩니다.

이 주제를 더 잘 이해하기 위해 예를 들어 보겠습니다. 병합 프로세스에 관련된 두 개의 하위 배열을 고려해 보겠습니다.

Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5

설명

배열의 반전 횟수

제공 n 배열, 그 역함수 찾기 턴 수. (i A[j])인 경우 쌍 (i, j)를 배열 A의 역전이라고 합니다. 우리는 arr

에서 이러한 모든 쌍을 계산해야 합니다. 예를 들어

배열

(9,6), (9,4), (9,5), (6,4), (6)에는 5개의 반전이 있습니다. ,5)

1. 요소의 값을 서로 비교해보세요.

2. 낮은 인덱스의 값이 더 높으면 카운터를 증가시킵니다.

3. 결과를 표시합니다.

예

#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
   int k = low, i = low, j = mid + 1;
   int inversionCount = 0;
   while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) {
         aux[k++] = arr[i++];
      } else {
         aux[k++] = arr[j++];
         inversionCount += (mid - i + 1); // NOTE
      }
   }
   while (i <= mid)
   aux[k++] = arr[i++];
   for (int i = low; i <= high; i++)
      arr[i] = aux[i];
   return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
   if (high == low) // if run size == 1
      return 0;
   int mid = (low + ((high - low) >> 1));
   int inversionCount = 0;
   inversionCount += MergeSort(arr, aux, low, mid);
   inversionCount += MergeSort(arr, aux, mid + 1, high);
   inversionCount += Merge(arr, aux, low, mid, high);
   return inversionCount;
}
int main() {
   int arr[] = { 1, 9, 6, 4, 5 };
   int N = 5;
   int aux[N];
   for (int i = 0; i < N; i++)
      aux[i] = arr[i];
   printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
   return 0;
}

위 내용은 배열의 역로그를 계산하기 위해 병합 정렬 알고리즘을 사용하여 작성된 C/C++ 프로그램이 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!