Dada una array arr[] , la tarea es encontrar el recuento total de inversiones significativas para la array. Dos elementos arr[i] y arr[j] forman una inversión significativa si arr[i] > 2 * arr[j] e i < j .
Ejemplos:
Entrada: arr[] = { 1, 20, 6, 4, 5 }
Salida: 3
Los pares de inversión significativos son (20, 6), (20, 5) y (20, 4).
Entrada: arr[] = { 1, 20 }
Salida: 0
Prerrequisito: Método de inversiones de conteo :
- La idea básica para encontrar inversiones se basará en el requisito previo anterior, utilizando el enfoque Divide and Conquer del tipo de fusión modificado .
- Se puede contar el número de inversiones significativas en la mitad izquierda y la mitad derecha. Incluir el conteo de inversión significativa con índice (i, j) tal que i esté en la mitad izquierda y j esté en la mitad derecha y luego sume los tres para obtener el conteo total de inversión significativa.
- El enfoque utilizado en el enlace anterior se puede modificar para realizar dos pases de la mitad izquierda y derecha durante el paso de fusión. En el primer paso, calcule el número de inversiones significativas en la array fusionada. Para cualquier índice i en la array izquierda si arr[i] > 2 * arr[j], entonces todos los elementos a la izquierda del i-ésimo índice en la array izquierda también contribuirán a un recuento de inversión significativo. Incremento j. De lo contrario incrementa i.
- El segundo paso será construir la array fusionada. Aquí se requieren dos pases porque en el conteo de inversión normal, los dos pases moverían i y j en los mismos puntos, por lo que se pueden combinar, pero eso no es cierto en este caso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);
// Function that sorts the input array
// and returns the number of inversions
// in the array
int mergeSort(int arr[], int array_size)
{
int temp[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
// Recursive function that sorts the input
// array and returns the number of
// inversions in the array
int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
// Divide the array into two parts and
// call _mergeSortAndCountInv()
// for each of the parts
mid = (right + left) / 2;
// Inversion count will be sum of the
// inversions in the left-part, the right-part
// and the number of inversions in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
// Merge the two parts
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
// Function that merges the two sorted arrays
// and returns the inversion count in the arrays
int merge(int arr[], int temp[], int left,
int mid, int right)
{
int i, j, k;
int inv_count = 0;
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// First pass to count number
// of significant inversions
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] > 2 * arr[j]) {
inv_count += (mid - i);
j++;
}
else {
i++;
}
}
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// Second pass to merge the two sorted arrays
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
// Copy the remaining elements of the left
// subarray (if there are any) to temp
while (i <= mid - 1)
temp[k++] = arr[i++];
// Copy the remaining elements of the right
// subarray (if there are any) to temp
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements to
// the original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
// Driver code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << mergeSort(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function that sorts the input array
// and returns the number of inversions
// in the array
static int mergeSort(int arr[], int array_size)
{
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
// Recursive function that sorts the input
// array and returns the number of
// inversions in the array
static int _mergeSort(int arr[], int temp[],
int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
// Divide the array into two parts and
// call _mergeSortAndCountInv()
// for each of the parts
mid = (right + left) / 2;
// Inversion count will be sum of the
// inversions in the left-part, the right-part
// and the number of inversions in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
// Merge the two parts
inv_count += merge(arr, temp, left,
mid + 1, right);
}
return inv_count;
}
// Function that merges the two sorted arrays
// and returns the inversion count in the arrays
static int merge(int arr[], int temp[], int left,
int mid, int right)
{
int i, j, k;
int inv_count = 0;
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// First pass to count number
// of significant inversions
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] > 2 * arr[j])
{
inv_count += (mid - i);
j++;
}
else
{
i++;
}
}
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// Second pass to merge the two sorted arrays
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
// Copy the remaining elements of the left
// subarray (if there are any) to temp
while (i <= mid - 1)
temp[k++] = arr[i++];
// Copy the remaining elements of the right
// subarray (if there are any) to temp
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements to
// the original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = arr.length;
System.out.println(mergeSort(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function that sorts the input array # and returns the number of inversions # in the array def mergeSort(arr, array_size): temp = [0 for i in range(array_size)] return _mergeSort(arr, temp, 0, array_size - 1) # Recursive function that sorts the input # array and returns the number of # inversions in the array def _mergeSort(arr, temp, left, right): mid, inv_count = 0, 0 if (right > left): # Divide the array into two parts and # call _mergeSortAndCountInv() # for each of the parts mid = (right + left) // 2 # Inversion count will be sum of the # inversions in the left-part, the right-part # and the number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid) inv_count += _mergeSort(arr, temp, mid + 1, right) # Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right) return inv_count # Function that merges the two sorted arrays # and returns the inversion count in the arrays def merge(arr, temp, left,mid, right): inv_count = 0 # i is the index for the left subarray i = left # j is the index for the right subarray j = mid # k is the index for the resultant # merged subarray k = left # First pass to count number # of significant inversions while ((i <= mid - 1) and (j <= right)): if (arr[i] > 2 * arr[j]): inv_count += (mid - i) j += 1 else: i += 1 # i is the index for the left subarray i = left # j is the index for the right subarray j = mid # k is the index for the resultant # merged subarray k = left # Second pass to merge the two sorted arrays while ((i <= mid - 1) and (j <= right)): if (arr[i] <= arr[j]): temp[k] = arr[i] i, k = i + 1, k + 1 else: temp[k] = arr[j] k, j = k + 1, j + 1 # Copy the remaining elements of the left # subarray (if there are any) to temp while (i <= mid - 1): temp[k] = arr[i] i, k = i + 1, k + 1 # Copy the remaining elements of the right # subarray (if there are any) to temp while (j <= right): temp[k] = arr[j] j, k = j + 1, k + 1 # Copy back the merged elements to # the original array for i in range(left, right + 1): arr[i] = temp[i] return inv_count # Driver code arr = [1, 20, 6, 4, 5] n = len(arr) print(mergeSort(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function that sorts the input array
// and returns the number of inversions
// in the array
static int mergeSort(int []arr,
int array_size)
{
int []temp = new int[array_size];
return _mergeSort(arr, temp, 0,
array_size - 1);
}
// Recursive function that sorts the input
// array and returns the number of
// inversions in the array
static int _mergeSort(int []arr, int []temp,
int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
// Divide the array into two parts and
// call _mergeSortAndCountInv()
// for each of the parts
mid = (right + left) / 2;
// Inversion count will be sum of the
// inversions in the left-part, the right-part
// and the number of inversions in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp,
mid + 1, right);
// Merge the two parts
inv_count += merge(arr, temp, left,
mid + 1, right);
}
return inv_count;
}
// Function that merges the two sorted arrays
// and returns the inversion count in the arrays
static int merge(int []arr, int []temp, int left,
int mid, int right)
{
int i, j, k;
int inv_count = 0;
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// First pass to count number
// of significant inversions
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] > 2 * arr[j])
{
inv_count += (mid - i);
j++;
}
else
{
i++;
}
}
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// Second pass to merge the two sorted arrays
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
// Copy the remaining elements of the left
// subarray (if there are any) to temp
while (i <= mid - 1)
temp[k++] = arr[i++];
// Copy the remaining elements of the right
// subarray (if there are any) to temp
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements to
// the original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
// Driver code
public static void Main ()
{
int []arr = { 1, 20, 6, 4, 5 };
int n = arr.Length;
Console.WriteLine(mergeSort(arr, n));
}
}
// This code is contributed by anuj_67..
Javascript
<script>
// Javascript implementation of the above approach
// Function that sorts the input array
// and returns the number of inversions
// in the array
function mergeSort(arr, array_size)
{
let temp = new Array(array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
// Recursive function that sorts the input
// array and returns the number of
// inversions in the array
function _mergeSort(arr, temp, left, right)
{
let mid, inv_count = 0;
if (right > left)
{
// Divide the array into two parts and
// call _mergeSortAndCountInv()
// for each of the parts
mid = parseInt((right + left) / 2, 10);
// Inversion count will be sum of the
// inversions in the left-part, the right-part
// and the number of inversions in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp,
mid + 1, right);
// Merge the two parts
inv_count += merge(arr, temp, left,
mid + 1, right);
}
return inv_count;
}
// Function that merges the two sorted arrays
// and returns the inversion count in the arrays
function merge(arr, temp, left, mid, right)
{
let i, j, k;
let inv_count = 0;
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// First pass to count number
// of significant inversions
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] > 2 * arr[j])
{
inv_count += (mid - i);
j++;
}
else
{
i++;
}
}
// i is the index for the left subarray
i = left;
// j is the index for the right subarray
j = mid;
// k is the index for the resultant
// merged subarray
k = left;
// Second pass to merge the two sorted arrays
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
// Copy the remaining elements of the left
// subarray (if there are any) to temp
while (i <= mid - 1)
temp[k++] = arr[i++];
// Copy the remaining elements of the right
// subarray (if there are any) to temp
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements to
// the original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
let arr = [ 1, 20, 6, 4, 5 ];
let n = arr.length;
document.write(mergeSort(arr, n));
// This code is contributed by mukesh07.
</script>
Producción:
3