Contar inversões em uma array | Conjunto 1 (usando mesclagem de classificação)
A contagem de inversão para um array indica - a que distância (ou perto) o array está de ser classificado. Se a array já estiver classificada, a contagem de inversão será 0, mas se a array for classificada na ordem inversa, a contagem de inversão será o máximo.
Falando formalmente, dois elementos a [i] e a [j] formam uma inversão se a [i]> a [j] e i <j
Exemplo:
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 (Simples)
- Abordagem: Percorra a array e, para cada índice, encontre o número de elementos menores à direita da array. Isso pode ser feito usando um loop aninhado. Some as contagens de todos os índices da array e imprima a soma.
- Algoritmo:
- Percorra a array do início ao fim
- Para cada elemento, encontre a contagem de elementos menores que o número atual até aquele índice usando outro loop.
- Some a contagem de inversão para cada índice.
- Imprima a contagem de inversões.
- Implementação:
// 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 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 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 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# 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 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
?><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>Saída
O número de inversões é 5
- Análise de complexidade:
- Complexidade de tempo: O (n ^ 2), dois loops aninhados são necessários para percorrer a array do início ao fim, então a complexidade de tempo é O (n ^ 2)
- Complexidade do espaço : O (1), nenhum espaço extra é necessário.
MÉTODO 2 (Melhorar classificação de fusão)
- Abordagem:
suponha o número de inversões na metade esquerda e na metade direita do array (sejam inv1 e inv2); que tipos de inversões não são contabilizados em Inv1 + Inv2? A resposta é - as inversões que precisam ser contadas durante a etapa de mesclagem. Portanto, para obter o número total de inversões que precisam ser adicionadas, é o número de inversões no subarray esquerdo, subarray direito e merge().
- Como obter o número de inversões em merge()?
No processo de mesclagem, let i é usado para indexar a subarray esquerda ej para a subarray direita. Em qualquer etapa em merge(), se a [i] for maior que a [j], então haverá (mid - i) inversões. porque os subarrays esquerdo e direito são classificados, então todos os elementos restantes no subarray esquerdo (a [i + 1], a [i + 2] ... a [mid]) serão maiores do que a [j]
- A imagem completa:
- Algoritmo:
- A ideia é semelhante à classificação por mesclagem, dividir a array em duas metades iguais ou quase iguais em cada etapa até que o caso base seja alcançado.
- Crie uma fusão de função que conta o número de inversões quando duas metades da array são mescladas, crie dois índices i e j, i é o índice da primeira metade ej é um índice da segunda metade. se a [i] é maior que a [j], então há (mid - i) inversões. porque os subarrays esquerdo e direito são classificados, então todos os elementos restantes no subarray esquerdo (a [i + 1], a [i + 2]… a [mid]) serão maiores do que a [j].
- Crie uma função recursiva para dividir a array em metades e encontre a resposta somando o número de inversões na primeira metade, o número de inversões na segunda metade e o número de inversões pela fusão das duas.
- O caso básico de recursão é quando há apenas um elemento na metade fornecida.
- Imprima a resposta
- Implementação:
// 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 funt 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 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 funt 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 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# 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# 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<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>
Saída:
Number of inversions are 5
Análise de complexidade:
- Complexidade de tempo: O (n log n), o algoritmo usado é dividir e conquistar, então, em cada nível, é necessária uma travessia de array completa e há log n níveis, então a complexidade de tempo é O (n log n).
- Complexidade do espaço : O (n), array temporário.
Observe que o código acima modifica (ou classifica) a array de entrada. Se quisermos contar apenas inversões, precisamos criar uma cópia do array original e chamar mergeSort() na cópia para preservar a ordem do array original.
Você pode gostar de ver:
Contar inversões em uma array | Conjunto 2 (usando BST com autobalanceamento)
Contando inversões usando Conjunto em C++ STL
Contar inversões em uma array | Conjunto 3 (usando BIT)
Referências:
http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
http://www.cp.eng.chula.ac.th/~ piak / learning / algo / algo2008 / count-inv.htm
Por favor, escreva comentários se você encontrar algum bug no programa / algoritmo acima ou outras maneiras de resolvê-lo.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
