El conteo de inversión para una array indica qué tan lejos (o cerca) está la array de ser ordenada. Si la array ya está ordenada, entonces el conteo de inversión es 0, pero si la array está ordenada en orden inverso, el conteo de inversión es el máximo.
Hablando formalmente, dos elementos a[i] y a[j] forman una inversión si a[i] > a[j] e i < j
Ejemplo:
Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions:
(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).
Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3, 1), (3, 2)
MÉTODO 1 (Simple)
- Enfoque: recorra la array y, para cada índice, encuentre la cantidad de elementos más pequeños en su lado derecho de la array. Esto se puede hacer usando un bucle anidado. Sume los recuentos de todos los índices de la array e imprima la suma.
- Algoritmo:
- Atraviesa la array de principio a fin
- Para cada elemento, encuentre el recuento de elementos más pequeños que el número actual hasta ese índice usando otro ciclo.
- Suma el recuento de inversión para cada índice.
- Imprime el conteo de inversiones.
- Implementación:
C++
// C++ program to Count Inversions
// in an array
#include <bits/stdc++.h>
using namespace std;
int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
// Driver Code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << " Number of inversions are "
<< getInvCount(arr, n);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C program to Count
// Inversions in an array
#include <stdio.h>
#include <stdlib.h>
int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(" Number of inversions are %d \n",
getInvCount(arr, n));
return 0;
}
Java
// Java program to count
// inversions in an array
class Test {
static int arr[] = new int[] { 1, 20, 6, 4, 5 };
static int getInvCount(int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.println("Number of inversions are "
+ getInvCount(arr.length));
}
}
Python3
# Python3 program to count
# inversions in an array
def getInvCount(arr, n):
inv_count = 0
for i in range(n):
for j in range(i + 1, n):
if (arr[i] > arr[j]):
inv_count += 1
return inv_count
# Driver Code
arr = [1, 20, 6, 4, 5]
n = len(arr)
print("Number of inversions are",
getInvCount(arr, n))
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to count inversions
// in an array
using System;
using System.Collections.Generic;
class GFG {
static int[] arr = new int[] { 1, 20, 6, 4, 5 };
static int getInvCount(int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
// Driver code
public static void Main()
{
Console.WriteLine("Number of "
+ "inversions are "
+ getInvCount(arr.Length));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to Count Inversions
// in an array
function getInvCount(&$arr, $n)
{
$inv_count = 0;
for ($i = 0; $i < $n - 1; $i++)
for ($j = $i + 1; $j < $n; $j++)
if ($arr[$i] > $arr[$j])
$inv_count++;
return $inv_count;
}
// Driver Code
$arr = array(1, 20, 6, 4, 5 );
$n = sizeof($arr);
echo "Number of inversions are ",
getInvCount($arr, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to count inversions in an array
arr = [1, 20, 6, 4, 5];
function getInvCount(arr){
let inv_count = 0;
for(let i=0; i<arr.length-1; i++){
for(let j=i+1; j<arr.length; j++){
if(arr[i] > arr[j]) inv_count++;
}
}
return inv_count;
}
// function call
document.write("Number of inversions are "+ getInvCount(arr));
// This code is contributed by Karthik SP
</script>
Producción
Number of inversions are 5
- Análisis de Complejidad:
- Complejidad de tiempo: O (n ^ 2), se necesitan dos bucles anidados para atravesar la array de principio a fin, por lo que la complejidad de tiempo es O (n ^ 2)
- Complejidad espacial : O(1), No se requiere espacio adicional.
MÉTODO 2 (Mejorar clasificación por fusión)
- Enfoque:
suponga el número de inversiones en la mitad izquierda y la mitad derecha de la array (sea inv1 e inv2); ¿Qué tipos de inversiones no se tienen en cuenta en Inv1 + Inv2? La respuesta es: las inversiones que deben contarse durante el paso de fusión. Por lo tanto, para obtener el número total de inversiones que se deben agregar, se debe agregar el número de inversiones en el subarreglo izquierdo, el subarreglo derecho y fusionar().
- ¿Cómo obtener el número de inversiones en merge()?
En el proceso de fusión, let i se usa para indexar el subconjunto izquierdo y j para el subconjunto derecho. En cualquier paso de merge(), si a[i] es mayor que a[j], entonces hay inversiones (mid – i). porque los subarreglos izquierdo y derecho están ordenados, por lo que todos los elementos restantes en el subarreglo izquierdo (a[i+1], a[i+2] … a[mid]) serán mayores que a[j]
- La imagen completa:
- Algoritmo:
- La idea es similar a la ordenación por fusión, divida la array en dos mitades iguales o casi iguales en cada paso hasta llegar al caso base.
- Cree una combinación de funciones que cuente el número de inversiones cuando se fusionan dos mitades de la array, cree dos índices i y j, i es el índice de la primera mitad y j es un índice de la segunda mitad. si a[i] es mayor que a[j], entonces hay inversiones (mid – i). porque los subarreglos izquierdo y derecho están ordenados, por lo que todos los elementos restantes en el subarreglo izquierdo (a[i+1], a[i+2] … a[mid]) serán mayores que a[j].
- Cree una función recursiva para dividir la array en mitades y encuentre la respuesta sumando el número de inversiones en la primera mitad, el número de inversiones en la segunda mitad y el número de inversiones fusionando los dos.
- El caso base de recursividad es cuando solo hay un elemento en la mitad dada.
- Imprime la respuesta
- Implementación:
C++
// C++ program to Count
// Inversions in an array
// using Merge Sort
#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);
/* This function 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);
}
/* An auxiliary 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
inversions in left-part, right-part
and 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;
}
/* This function merges two sorted arrays
and returns 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 = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/* this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to 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]);
int ans = mergeSort(arr, n);
cout << " Number of inversions are " << ans;
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to Count
// Inversions in an array
// using Merge Sort
#include <stdio.h>
#include <stdlib.h>
int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid,
int right);
/* This function sorts the input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
int* temp = (int*)malloc(sizeof(int) * array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary 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 the sum of inversions in
left-part, right-part and 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;
}
/* This function merges two sorted
arrays and returns 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 = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* Driver code*/
int main(int argv, char** args)
{
int arr[] = { 1, 20, 6, 4, 5 };
printf(" Number of inversions are %d \n",
mergeSort(arr, 5));
getchar();
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
public class GFG {
// Function to count the number of inversions
// during the merge process
private static int mergeAndCount(int[] arr, int l,
int m, int r)
{
// Left subarray
int[] left = Arrays.copyOfRange(arr, l, m + 1);
// Right subarray
int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
int i = 0, j = 0, k = l, swaps = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else {
arr[k++] = right[j++];
swaps += (m + 1) - (l + i);
}
}
while (i < left.length)
arr[k++] = left[i++];
while (j < right.length)
arr[k++] = right[j++];
return swaps;
}
// Merge sort function
private static int mergeSortAndCount(int[] arr, int l,
int r)
{
// Keeps track of the inversion count at a
// particular node of the recursion tree
int count = 0;
if (l < r) {
int m = (l + r) / 2;
// Total inversion count = left subarray count
// + right subarray count + merge count
// Left subarray count
count += mergeSortAndCount(arr, l, m);
// Right subarray count
count += mergeSortAndCount(arr, m + 1, r);
// Merge count
count += mergeAndCount(arr, l, m, r);
}
return count;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 20, 6, 4, 5 };
System.out.println(
mergeSortAndCount(arr, 0, arr.length - 1));
}
}
// This code is contributed by Pradip Basak
Python3
# Python 3 program to count inversions in an array
# Function to Use Inversion Count
def mergeSort(arr, n):
# A temp_arr is created to store
# sorted array in merge function
temp_arr = [0]*n
return _mergeSort(arr, temp_arr, 0, n-1)
# This Function will use MergeSort to count inversions
def _mergeSort(arr, temp_arr, left, right):
# A variable inv_count is used to store
# inversion counts in each recursive call
inv_count = 0
# We will make a recursive call if and only if
# we have more than one elements
if left < right:
# mid is calculated to divide the array into two subarrays
# Floor division is must in case of python
mid = (left + right)//2
# It will calculate inversion
# counts in the left subarray
inv_count += _mergeSort(arr, temp_arr,
left, mid)
# It will calculate inversion
# counts in right subarray
inv_count += _mergeSort(arr, temp_arr,
mid + 1, right)
# It will merge two subarrays in
# a sorted subarray
inv_count += merge(arr, temp_arr, left, mid, right)
return inv_count
# This function will merge two subarrays
# in a single sorted subarray
def merge(arr, temp_arr, left, mid, right):
i = left # Starting index of left subarray
j = mid + 1 # Starting index of right subarray
k = left # Starting index of to be sorted subarray
inv_count = 0
# Conditions are checked to make sure that
# i and j don't exceed their
# subarray limits.
while i <= mid and j <= right:
# There will be no inversion if arr[i] <= arr[j]
if arr[i] <= arr[j]:
temp_arr[k] = arr[i]
k += 1
i += 1
else:
# Inversion will occur.
temp_arr[k] = arr[j]
inv_count += (mid-i + 1)
k += 1
j += 1
# Copy the remaining elements of left
# subarray into temporary array
while i <= mid:
temp_arr[k] = arr[i]
k += 1
i += 1
# Copy the remaining elements of right
# subarray into temporary array
while j <= right:
temp_arr[k] = arr[j]
k += 1
j += 1
# Copy the sorted subarray into Original array
for loop_var in range(left, right + 1):
arr[loop_var] = temp_arr[loop_var]
return inv_count
# Driver Code
# Given array is
arr = [1, 20, 6, 4, 5]
n = len(arr)
result = mergeSort(arr, n)
print("Number of inversions are", result)
# This code is contributed by ankush_953
C#
// C# implementation of counting the
// inversion using merge sort
using System;
public class Test {
/* This method 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);
}
/* An auxiliary recursive method 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 the sum of inversions
in left-part, right-part
and 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;
}
/* This method merges two sorted arrays and returns
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 = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged
subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
// Driver method to test the above function
public static void Main()
{
int[] arr = new int[] { 1, 20, 6, 4, 5 };
Console.Write("Number of inversions are "
+ mergeSort(arr, 5));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Function to count the number of inversions
// during the merge process
function mergeAndCount(arr,l,m,r)
{
// Left subarray
let left = [];
for(let i = l; i < m + 1; i++)
{
left.push(arr[i]);
}
// Right subarray
let right = [];
for(let i = m + 1; i < r + 1; i++)
{
right.push(arr[i]);
}
let i = 0, j = 0, k = l, swaps = 0;
while (i < left.length && j < right.length)
{
if (left[i] <= right[j])
{
arr[k++] = left[i++];
}
else
{
arr[k++] = right[j++];
swaps += (m + 1) - (l + i);
}
}
while (i < left.length)
{
arr[k++] = left[i++];
}
while (j < right.length)
{
arr[k++] = right[j++];
}
return swaps;
}
// Merge sort function
function mergeSortAndCount(arr, l, r)
{
// Keeps track of the inversion count at a
// particular node of the recursion tree
let count = 0;
if (l < r)
{
let m = Math.floor((l + r) / 2);
// Total inversion count = left subarray count
// + right subarray count + merge count
// Left subarray count
count += mergeSortAndCount(arr, l, m);
// Right subarray count
count += mergeSortAndCount(arr, m + 1, r);
// Merge count
count += mergeAndCount(arr, l, m, r);
}
return count;
}
// Driver code
let arr= new Array(1, 20, 6, 4, 5 );
document.write(mergeSortAndCount(arr, 0, arr.length - 1));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Number of inversions are 5
Análisis de Complejidad:
- Complejidad de tiempo: O (n log n), el algoritmo utilizado es divide y vencerás, por lo que en cada nivel, se necesita un recorrido de array completo y hay niveles de log n, por lo que la complejidad de tiempo es O (n log n).
- Complejidad espacial : O(n), array temporal.
Tenga en cuenta que el código anterior modifica (u ordena) la array de entrada. Si queremos contar solo las inversiones, debemos crear una copia de la array original y llamar a mergeSort() en la copia para conservar el orden de la array original.
MÉTODO 3 (Heapsort + Bisección)
- Algoritmo:
- Cree un montón con nuevos elementos de par, (elemento, índice).
- Después de ordenarlos, extraiga cada mínimo de forma secuencial y cree una nueva lista ordenada con los índices.
- Calcule la diferencia entre el índice original y el índice de bisección de la nueva lista ordenada.
- Resuma la diferencia.
Python3
from heapq import heappush, heappop
from bisect import bisect, insort
def getNumOfInversions(A):
N = len(A)
if N <= 1:
return 0
sortList = []
result = 0
# heapsort, O(N*log(N))
for i, v in enumerate(A):
heappush(sortList, (v, i))
x = [] # create a sorted list of indexes
while sortList: # O(N)
v, i = heappop(sortList) # O(log(N))
# find the current minimum's index
# the index y can represent how many minimums on the left
y = bisect(x, i) # O(log(N))
# i can represent how many elements on the left
# i - y can find how many bigger nums on the left
result += i - y
insort(x, i) # O(log(N))
return result
# Driver Code
# Given array is
A = [-1, 6, 3, 4, 7, 4]
result = getNumOfInversions(A)
print(f'Number of inversions are {result}')
Análisis de Complejidad:
- Complejidad temporal: O(n log n). Tanto heapsort como bisection pueden realizar una inserción ordenada en log n en cada elemento, por lo que la complejidad de tiempo es O (n log n).
- Complejidad espacial: O(n). Un montón y una nueva lista tienen la misma longitud que la array original.
Puede que le guste ver:
Contar inversiones en una array | Conjunto 2 (usando BST de autoequilibrio)
Contando inversiones usando Conjunto en C++ STL
Contar inversiones en una array | Conjunto 3 (usando BIT)
Escriba comentarios si encuentra algún error en el programa/algoritmo anterior u otras formas de resolverlo.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA