Program C/C++ yang ditulis menggunakan algoritma isihan gabungan untuk mengira nombor terbalik dalam tatasusunan

Perwakilan songsang bagi tatasusunan; Apabila tatasusunan sudah diisih, 0 pembalikan diperlukan, manakala dalam kes lain, jika tatasusunan diterbalikkan, bilangan pembalikan maksimum dicapai.

Untuk menyelesaikan masalah ini, kami akan mengikuti kaedah isihan gabungan untuk mengurangkan kerumitan masa dan menggunakan algoritma bahagi dan takluk.

Input

A sequence of numbers. (1, 5, 6, 4, 20).

Output

Bilangan pembalikan yang diperlukan untuk mengisih nombor dalam tertib menaik.

Here the number of inversions are 2.
First inversion: (1, 5, 4, 6, 20)
Second inversion: (1, 4, 5, 6, 20)

Algoritma

cantum(array, tempArray, left, mid, right)

Input - dua tatasusunan, yang telah digabungkan, kiri, kanan dan indeks tengah.

Output - tatasusunan digabungkan dalam susunan disusun.

Begin
   i := left, j := mid, k := right
   count := 0
   while i <= mid -1 and j <= right, do
      if array[i] <= array[j], then
         tempArray[k] := array[i]
         increase i and k by 1
      else
         tempArray[k] := array[j]
         increase j and k by 1
         count := count + (mid - i)
   done
   while left part of the array has some extra element, do
      tempArray[k] := array[i]
      increase i and k by 1
   done
   while right part of the array has some extra element, do
      tempArray[k] := array[j]
      increase j and k by 1
   done
   return count
End

mergeSort(array, tempArray, left, right)

Input - Diberi tatasusunan dan tatasusunan sementara, indeks kiri dan kanan tatasusunan.

Output - Bilangan pasangan tertib terbalik selepas diisih.

Begin
   count := 0
   if right > left, then
      mid := (right + left)/2
      count := mergeSort(array, tempArray, left, mid)
      count := count + mergeSort(array, tempArray, mid+1, right)
      count := count + merge(array, tempArray, left, mid+1, right)
   return count
End

Contoh

Demonstrasi masa nyata

#include <iostream>
using namespace std;
int merge(int arr[], int temp[], int left, int mid, int right) {
   int i, j, k;
   int count = 0;
   i = left; //i to locate first array location
   j = mid; //i to locate second array location
   k = left; //i to locate merged array location
   while ((i <= mid - 1) && (j <= right)) {
      if (arr[i] <= arr[j]){ //when left item is less than right item
      temp[k++] = arr[i++];
      } else {
         temp[k++] = arr[j++];
         count += (mid - i); //find how many convertion is performed
      }
   }
   while (i <= mid - 1) //if first list has remaining item, add them in the list
      temp[k++] = arr[i++];
   while (j <= right) //if second list has remaining item, add them in the list
      temp[k++] = arr[j++];
   for (i=left; i <= right; i++)
      arr[i] = temp[i]; //store temp Array to main array
   return count;
}
int mergeSort(int arr[], int temp[], int left, int right){
   int mid, count = 0;
   if (right > left) {
      mid = (right + left)/2; //find mid index of the array
      count = mergeSort(arr, temp, left, mid); //merge sort left sub array
      count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
      count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
   }
   return count;
}
int arrInversion(int arr[], int n) {
   int temp[n];
   return mergeSort(arr, temp, 0, n - 1);
}
int main() {
   int arr[] = {1, 5, 6, 4, 20};
   int n = 5;
   cout << "Number of inversions are "<< arrInversion(arr, n);
}

Output

Number of inversions are 2

Atas ialah kandungan terperinci Program C/C++ yang ditulis menggunakan algoritma isihan gabungan untuk mengira nombor terbalik dalam tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!