Verifique si una array se puede ordenar intercambiando elementos adyacentes de modo que cada elemento se intercambie un número par de veces

Dada una array arr[] que consta de N enteros, la tarea es verificar si la array se puede ordenar intercambiando elementos adyacentes cualquier cantidad de veces, de modo que cada elemento de la array se intercambie incluso varias veces.

Ejemplos:

Entrada: arr[] = {4, 3, 2, 5}
Salida: Sí
Explicación:
A continuación se muestra el posible orden de intercambio para ordenar la array:

1. Elija los índices 0 y 1 modifica la array a [3, 4, 2, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {0, 1, 1, 0} respectivamente.
2. Elegir los índices 1 y 2 modifica la array a [3, 2, 4, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {1, 1, 2, 0} respectivamente.
3. Elija los índices 0 y 1 modifica la array a [2, 3, 4, 5]. Ahora, la frecuencia de intercambio de {2, 3, 4, 5} es {2, 2, 2, 0} respectivamente.

Por lo tanto, cada elemento de la array se intercambia un número par de veces y se ordena la array dada. Por lo tanto, imprima Sí.

Entrada: arr[] = {1, 2, 3, 5, 4}
Salida: No

Enfoque: El problema dado puede resolverse observando el hecho de que dos elementos de índices pares o impares adyacentes pueden intercambiarse ya que no hay restricción en el número de intercambios sin cambiar el elemento central. Por lo tanto, la idea es reorganizar el elemento de la array en los respectivos índices pares e impares y verificar si la array formada está ordenada o no. Siga los pasos a continuación para resolver el problema dado:

• Almacene todos los elementos de la array arr[i] en los índices impares en otra array, digamos odd[] .
• Almacene todos los elementos de la array arr[i] en los índices pares en otra array, digamos even[] .
• Ordene las arrays impar[] y par[] en orden creciente.
• inicialice dos variables, digamos j y k como 0 que se usa para recorrer las arrays odd[] y even[] .
• Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
  • Si el valor de i es impar, inserte el elemento impar[j] en la array res[] e incremente el valor de j en 1 .
  • Si el valor de i es par , empuje el elemento par[k] en la array res[] e incremente el valor de j en 1 .
• Después de completar los pasos anteriores, si la array res[] está ordenada, imprima Yes . De lo contrario , imprima No.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Function to check if the array can be
// made sorted by adjacent swapping of
// element such that each array element
// is swapped even number of times
bool isSorted(int arr[], int n)
{
    vector<int> evenArr, oddArr;
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // Stores all the even positions
        // elements
        if (i % 2 == 0)
            evenArr.push_back(arr[i]);
 
        // Stores all the odd positions
        // elements
        else
            oddArr.push_back(arr[i]);
    }
 
    // Sort the array evenArr[]
    sort(evenArr.begin(), evenArr.end());
 
    // Sort the array oddArr[]
    sort(oddArr.begin(), oddArr.end());
 
    int j = 0, k = 0;
    vector<int> res;
 
    // Combine the elements from evenArr
    // and oddArr in the new array res[]
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0)
            res.push_back(evenArr[j]), j++;
        else
            res.push_back(oddArr[k]), k++;
    }
 
    // Check if the array res[] is
    // sorted or not
    for (int i = 0; i < n - 1; i++) {
        if (res[i] > res[i + 1])
            return false;
    }
 
    // Otherwise, return true
    return true;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 3, 2, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    if (isSorted(arr, N)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if the array can be
// made sorted by adjacent swapping of
// element such that each array element
// is swapped even number of times
static boolean isSorted(int arr[], int n)
{
    Vector<Integer> evenArr = new Vector<Integer>();
    Vector<Integer> oddArr = new Vector<Integer>();
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // Stores all the even positions
        // elements
        if (i % 2 == 0)
            evenArr.add(arr[i]);
 
        // Stores all the odd positions
        // elements
        else
            oddArr.add(arr[i]);
    }
 
    // Sort the array evenArr[]
    Collections.sort(evenArr);
 
    // Sort the array oddArr[]
    Collections.sort(oddArr);
 
    int j = 0, k = 0;
    Vector<Integer> res=new Vector<Integer>();;
 
    // Combine the elements from evenArr
    // and oddArr in the new array res[]
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            res.add(evenArr.get(j)); j++;
        }
        else {
            res.add(oddArr.get(k)); k++;
        }
    }
 
    // Check if the array res[] is
    // sorted or not
    for (int i = 0; i < n - 1; i++) {
        if (res.get(i) > res.get(i + 1))
            return false;
    }
 
    // Otherwise, return true
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 4, 3, 2, 5 };
    int N = arr.length;
 
    if (isSorted(arr, N)) {
        System.out.print("Yes");
    }
    else {
        System.out.print("No");
    }
 
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to check if the array can be
# made sorted by adjacent swapping of
# element such that each array element
# is swapped even number of times
def isSorted(arr, n):
     
    evenArr = []
    oddArr = []
 
    # Traverse the given array
    for i in range(n):
         
        # Stores all the even positions
        # elements
        if (i % 2 == 0):
            evenArr.append(arr[i])
 
        # Stores all the odd positions
        # elements
        else:
            oddArr.append(arr[i])
 
    # Sort the array evenArr[]
    evenArr.sort()
 
    # Sort the array oddArr[]
    oddArr.sort()
 
    j = 0
    k = 0
    res = []
 
    # Combine the elements from evenArr
    # and oddArr in the new array res[]
    for i in range(n):
        if (i % 2 == 0):
            res.append(evenArr[j])
            j += 1
        else:
            res.append(oddArr[k])
            k += 1
 
    # Check if the array res[] is
    # sorted or not
    for i in range(n - 1):
        if (res[i] > res[i + 1]):
            return False
 
    # Otherwise, return true
    return True
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 4, 3, 2, 5 ]
    N = len(arr)
 
    if (isSorted(arr, N)):
        print("Yes")
    else:
        print("No")
         
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
   
    // Function to check if the array can be
    // made sorted by adjacent swapping of
    // element such that each array element
    // is swapped even number of times
    static bool isSorted(int[] arr, int n)
    {
        List<int> evenArr = new List<int>();
        List<int> oddArr = new List<int>();
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // Stores all the even positions
            // elements
            if (i % 2 == 0)
                evenArr.Add(arr[i]);
 
            // Stores all the odd positions
            // elements
            else
                oddArr.Add(arr[i]);
        }
 
        // Sort the array evenArr[]
        evenArr.Sort();
 
        // Sort the array oddArr[]
        oddArr.Sort();
 
        int j = 0, k = 0;
        List<int> res = new List<int>();
 
        // Combine the elements from evenArr
        // and oddArr in the new array res[]
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res.Add(evenArr[j]);
                j++;
            }
            else {
                res.Add(oddArr[k]);
                k++;
            }
        }
 
        // Check if the array res[] is
        // sorted or not
        for (int i = 0; i < n - 1; i++) {
            if (res[i] > res[i + 1])
                return false;
        }
 
        // Otherwise, return true
        return true;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 4, 3, 2, 5 };
        int N = arr.Length;
 
        if (isSorted(arr, N)) {
            Console.Write("Yes");
        }
        else {
            Console.Write("No");
        }
    }
}
 
// This code is contributed by ukasp.

<script>
 
        // JavaScript program for the above approach;
 
 
        // Function to check if the array can be
        // made sorted by adjacent swapping of
        // element such that each array element
        // is swapped even number of times
        function isSorted(arr, n) {
            let evenArr = [], oddArr = [];
 
            // Traverse the given array
            for (let i = 0; i < n; i++) {
 
                // Stores all the even positions
                // elements
                if (i % 2 == 0)
                    evenArr.push(arr[i]);
 
                // Stores all the odd positions
                // elements
                else
                    oddArr.push(arr[i]);
            }
 
            // Sort the array evenArr[]
            evenArr.sort(function (a, b) { return a - b });
 
            // Sort the array oddArr[]
            oddArr.sort(function (a, b) { return a - b });
 
            let j = 0, k = 0;
            let res = [];
 
            // Combine the elements from evenArr
            // and oddArr in the new array res[]
            for (let i = 0; i < n; i++) {
                if (i % 2 == 0)
                    res.push(evenArr[j]), j++;
                else
                    res.push(oddArr[k]), k++;
            }
 
            // Check if the array res[] is
            // sorted or not
            for (let i = 0; i < n - 1; i++) {
                if (res[i] > res[i + 1])
                    return false;
            }
 
            // Otherwise, return true
            return true;
        }
 
        // Driver Code
 
        let arr = [4, 3, 2, 5];
        let N = arr.length;
 
        if (isSorted(arr, N)) {
            document.write("Yes");
        }
        else {
            document.write("No");
        }
 
 
   // This code is contributed by Potta Lokesh
    </script>

Yes

Complejidad temporal: O(N*log N)
Espacio auxiliar: O(N)