Dada una array de valores enteros que deben ordenarse mediante una sola operación: rotación de subarreglo donde el tamaño del subarreglo debe ser 3. Por ejemplo, si nuestra array es (1 2 3 4), entonces podemos llegar a (1 4 2 3), (3 1 2 4) en un solo paso. Necesitamos decir si es posible ordenar la array completa con esta operación o no.
Ejemplos:
Input : arr[] = [1, 3, 4, 2] Output : Yes Possible by below rotations, [1, 3, 4, 2] -> [1, 4, 2, 3] -> [1, 2, 3, 4] Input : arr[] = [1, 2, 4, 3] Output : No Not possible to sort above array by any 3 size subarray rotation.
Supongamos que tenemos un subarreglo como [A[i] A[i+1] A[i+2]]. Después de una rotación, obtenemos [A[i+2], A[i], A[i+1]]
Si observamos las inversiones antes y después de la rotación, podemos ver que la paridad de la inversión no cambia, es decir, si [A[i] A[i+1] A[i+2]] tiene un número par de inversiones [A[i+2] ] A[i] A[i+1]] tendrá inversiones pares. Lo mismo es cierto para las inversiones impares. Debido al movimiento de A[i+2], las inversiones aumentan en 2 o disminuyen en 2 o permanecen iguales, es decir, su paridad no cambiará.
Después de observar el hecho anterior, podemos decir que si la configuración inicial de la array tiene un número par de inversiones, entonces es posible hacer que la array sea cero, de lo contrario, no se ordenará por completo. Utilizamos el método basado en la clasificación por combinación para contar las inversiones . Después de obtener el número de inversiones, podemos verificar fácilmente la paridad de la inversión y concluir si es posible ordenar la array o no.
Implementación:
C++
// C++ program to check whether we can sort
// given array using 3 size subarray rotation
// or not
#include <bits/stdc++.h>
using namespace std;
/* 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;
}
/* 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 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);
}
// method returns true is array can be sorted by 3
// size subarray rotation
bool possibleSortingBy3SizeSubarray(int arr[], int N)
{
int numberOfInversion = mergeSort(arr, N);
// if number of inversions are even then only
// we can sort the array
return (numberOfInversion % 2 == 0);
}
// Driver code to test above methods
int main()
{
int arr[] = {1, 3, 4, 2};
int N = sizeof(arr) / sizeof(int);
possibleSortingBy3SizeSubarray(arr, N)?
cout << "Yes\n" : cout << "No\n";
}
Java
// Java program to check whether we can sort
// given array using 3 size subarray rotation
// or not
import java.io.*;
class GFG
{
/* This function merges two sorted arrays and
returns inversion count in the arrays.*/
public static int merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[arr.length];
int inv_count = 0;
int i = left; /* i is index for left subarray*/
int j = mid; /* j is index for right subarray*/
int k = left; /* k is index for resultant merged
subarray*/
while((i <= mid-1) && (j <= right))
{
if(arr[i] <= arr[j])
{
temp[k++] = arr[i];
i++;
}
else
{
temp[k++] = arr[j];
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 (int l = left; l <= right; l++)
arr[l] = temp[l];
return inv_count;
}
/* An auxiliary recursive function that sorts
the input array and returns the number of
inversions in the array. */
public static int _mergeSort(int[] arr, int left, int right)
{
int mid, inv_count = 0;
if(left < right)
{
/* Divide the array into two parts and
call _mergeSortAndCountInv() for each
of the parts */
mid = (left + right)/2;
/* Inversion count will be sum of inversions
in left-part, right-part and number of
inversions in merging */
inv_count = _mergeSort(arr, left, mid);
inv_count += _mergeSort(arr, mid+1, right);
inv_count += merge(arr, left, mid+1, right);
}
return inv_count;
}
/* This function sorts the input array and returns the
number of inversions in the array */
public static int mergeSort(int[] arr, int N)
{
return _mergeSort(arr, 0, N-1);
}
public static boolean possibleSortingBy3SizeSubarray(int arr[], int N)
{
int numberOfInversion = mergeSort(arr, N);
// if number of inversions are even then only
// we can sort the array
return (numberOfInversion % 2 == 0);
}
// Driver code to test above methods
public static void main (String[] args)
{
int arr[] = {1, 3, 4, 2};
int N = arr.length;
if(possibleSortingBy3SizeSubarray(arr, N))
System.out.println( "Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to check whether we can sort
# given array using 3 size subarray rotation or not
# This function merges two sorted arrays and
# returns inversion count in the arrays.
def merge(arr, temp, left, mid, right):
# i is index for left subarray
# j is index for right subarray
# k is index for resultant merged subarray
i, j, k, inv_count = left, mid, left, 0
while (i <= mid - 1) and (j <= right):
if arr[i] <= arr[j]:
temp[k] = arr[i]
k, i = k + 1, i + 1
else:
temp[k] = arr[j]
k, j = k + 1, j + 1
# 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]
k, i = k + 1, i + 1
# Copy the remaining elements of right
# subarray (if there are any) to temp
while j <= right:
temp[k] = arr[j]
k, j = k + 1, j + 1
# Copy back the merged elements
# to original array
for i in range(left, right + 1):
arr[i] = temp[i]
return inv_count
# An auxiliary recursive function that
# sorts the input array and returns the
# number of inversions in the array.
def _mergeSort(arr, temp, left, right):
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 sorts the input array and
# returns the number of inversions in the array
def mergeSort(arr, array_size):
temp = [None] * array_size
return _mergeSort(arr, temp, 0, array_size - 1)
# method returns true is array can be
# sorted by 3 size subarray rotation
def possibleSortingBy3SizeSubarray(arr, N):
numberOfInversion = mergeSort(arr, N)
# if number of inversions are even
# then only we can sort the array
return (numberOfInversion % 2 == 0)
# Driver Code
if __name__ == "__main__":
arr = [1, 3, 4, 2]
N = len(arr)
if possibleSortingBy3SizeSubarray(arr, N):
print("Yes")
else:
print("No")
# This code is contributed by Rituraj Jain
C#
// C# program to check whether we
// can sort given array using 3 size
// subarray rotation or not.
using System;
class GFG
{
/* This function merges two sorted arrays and
returns inversion count in the arrays.*/
public static int merge(int []arr, int left,
int mid, int right)
{
int []temp = new int[arr.Length];
int inv_count = 0;
/* i is index for left subarray*/
int i = left;
/* j is index for right subarray*/
int j = mid;
/* k is index for resultant merged subarray*/
int k = left;
while((i <= mid-1) && (j <= right))
{
if(arr[i] <= arr[j])
{
temp[k++] = arr[i];
i++;
}
else
{
temp[k++] = arr[j];
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 (int l = left; l <= right; l++)
arr[l] = temp[l];
return inv_count;
}
/* An auxiliary recursive function that sorts
the input array and returns the number of
inversions in the array. */
public static int _mergeSort(int []arr, int left,
int right)
{
int mid, inv_count = 0;
if(left < right)
{
/* Divide the array into two parts and
call _mergeSortAndCountInv() for each
of the parts */
mid = (left + right)/2;
/* Inversion count will be sum of inversions
in left-part, right-part and number of
inversions in merging */
inv_count = _mergeSort(arr, left, mid);
inv_count += _mergeSort(arr, mid+1, right);
inv_count += merge(arr, left, mid+1, right);
}
return inv_count;
}
/* This function sorts the input array
and returns the number of inversions
in the array */
public static int mergeSort(int[] arr, int N)
{
return _mergeSort(arr, 0, N-1);
}
public static bool possibleSortingBy3SizeSubarray(int []arr,
int N)
{
int numberOfInversion = mergeSort(arr, N);
// if number of inversions are even
// then only we can sort the array
return (numberOfInversion % 2 == 0);
}
// Driver code to test above methods
public static void Main ()
{
int []arr = {1, 3, 4, 2};
int N = arr.Length;
if(possibleSortingBy3SizeSubarray(arr, N))
Console.Write( "Yes");
else
Console.Write("No");
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// JavaScript program to check whether we can sort
// given array using 3 size subarray rotation
// or not
/* This function merges two sorted arrays and
returns inversion count in the arrays.*/
function merge(arr, left, mid, right) {
let temp = new Array(arr.length);
let inv_count = 0;
let i = left; /* i is index for left subarray*/
let j = mid; /* j is index for right subarray*/
let k = left; /* k is index for resultant merged
subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i];
i++;
}
else {
temp[k++] = arr[j];
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 (let l = left; l <= right; l++)
arr[l] = temp[l];
return inv_count;
}
/* An auxiliary recursive function that sorts
the input array and returns the number of
inversions in the array. */
function _mergeSort(arr, left, right) {
let mid, inv_count = 0;
if (left < right) {
/* Divide the array into two parts and
call _mergeSortAndCountInv() for each
of the parts */
mid = Math.floor((left + right) / 2);
/* Inversion count will be sum of inversions
in left-part, right-part and number of
inversions in merging */
inv_count = _mergeSort(arr, left, mid);
inv_count += _mergeSort(arr, mid + 1, right);
inv_count += merge(arr, left, mid + 1, right);
}
return inv_count;
}
/* This function sorts the input array and returns the
number of inversions in the array */
function mergeSort(arr, N) {
return _mergeSort(arr, 0, N - 1);
}
function possibleSortingBy3SizeSubarray(arr, N) {
let numberOfInversion = mergeSort(arr, N);
// if number of inversions are even then only
// we can sort the array
return (numberOfInversion % 2 == 0);
}
// Driver code to test above methods
let arr = [1, 3, 4, 2];
let N = arr.length;
if (possibleSortingBy3SizeSubarray(arr, N))
document.write("Yes");
else
document.write("No");
</script>
Producción
Yes
Complejidad de tiempo: O (n Log n)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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