Inversiones significativas en un arreglo

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:
Los pares de inversión significativos son (20, 6), (20, 5) y (20, 4).
Entrada: arr[] = { 1, 20 } 
Salida:
 

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

 

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *