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

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

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

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

설명

배열의 반전 횟수

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

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

< p> 배열

(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 중국어 웹사이트의 기타 관련 기사를 참조하세요!