Compruebe si la array se puede ordenar intercambiando elementos adyacentes de paridad opuesta

Dada una array A de tamaño n , la tarea es verificar si la array se puede ordenar en orden creciente, si la única operación permitida es intercambiar los elementos adyacentes si son de paridad opuesta. La operación se puede hacer cualquier número de veces.

Ejemplos :

Entrada : n = 4, A = [1, 6, 51, 16]
Salida : SÍ
Explicación : Dado que 51 es impar y 16 es par, simplemente los intercambiaremos. La array ahora se convierte en [1, 6, 16, 51], que se ordena en orden creciente.

Entrada : n = 4, A = [5, 5, 5, 5]
Salida : SÍ
Explicación : la array ya está ordenada.

 

Enfoque: se puede observar que si el orden de los elementos pares o el orden de los elementos impares es decreciente, entonces sería imposible ordenar la array. 

Podemos suponer que vamos a ordenar la array utilizando la clasificación de burbujas (como en la clasificación de burbujas también, los elementos adyacentes se intercambian hasta que obtengamos una array ordenada). En la ordenación de burbuja, si el elemento A[i]>A[j] (donde, i<j), entonces en cualquier punto durante las iteraciones, están obligados a intercambiarse. Pero, aquí tenemos una restricción, que no podemos intercambiar elementos de paridad similares. Entonces, si alguno de los mismos elementos de paridad está en orden decreciente, sería imposible ordenar la array. 

Siga los pasos a continuación para resolver el problema: 

  • Cree 2 variables denominadas «impar» y «par» para almacenar los elementos pares e impares anteriores, respectivamente.
  • Iterar a través de la array.
  • En cada iteración, verifique si el elemento es par o impar y compárelo con el elemento par o impar anterior, respectivamente.
  • Si el elemento par/impar actual es menor que el elemento par/impar anterior, devuelve falso.
  • Si la iteración finaliza, devuelve verdadero, ya que sería posible ordenar la array,

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

C++

// C++ Code for the Check if array can be
// sorted by swapping adjacent elements
// of opposite parity
#include <bits/stdc++.h>
using namespace std;
 
// function to check if the array can be
// sorted in increasing order by
// swappingadjacent elements of same parity
bool canBeSorted(int n, int A[])
{
    // declaring & initializing odd and
    // even variables, that stores previous
    // odd and even elements respectively
    int odd = -1, even = -1;
 
    // declaring and initializing flag
    // variable to store the answer
    int flag = 1;
 
    // iterating through the array
    for (int i = 0; i < n; i++) {
 
        // if the element is odd
        if (A[i] % 2 == 1) {
            if (A[i] < odd) {
                flag = 0;
                break;
            }
 
            // if it is less than previous
            // odd element, then array can
            // not be sorted
            else {
                // else we update the last
                // odd element
                odd = A[i];
            }
        }
 
        // if the element is even
        else {
            if (A[i] < even) {
                flag = 0;
                break;
            }
 
            // if it is less than previous
            // even element, then array can
            // not be sorted
            even = A[i];
 
            // else we update
            // the last even element
        }
    }
 
    // all even elements are sorted and all
    // odd elements are sorted, hence we
    // return true as it is possible to
    // sort the array
    if (flag) {
        return true;
    }
 
    // not possible to sort the array
    return false;
}
 
// Driver Code
int main()
{
    int n = 4;
    int A[] = { 1, 6, 51, 16 };
    bool answer = canBeSorted(n, A);
 
    if (answer == 1) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
}

Java

// Java Code for the Check if array can be
// sorted by swapping adjacent elements
// of opposite parity
import java.io.*;
 
class GFG {
 
  // function to check if the array can be
  // sorted in increasing order by
  // swappingadjacent elements of same parity
  static Boolean canBeSorted(int n, int A[])
  {
    // declaring & initializing odd and
    // even variables, that stores previous
    // odd and even elements respectively
    int odd = -1, even = -1;
 
    // declaring and initializing flag
    // variable to store the answer
    int flag = 1;
 
    // iterating through the array
    for (int i = 0; i < n; i++) {
 
      // if the element is odd
      if (A[i] % 2 == 1) {
        if (A[i] < odd) {
          flag = 0;
          break;
        }
 
        // if it is less than previous
        // odd element, then array can
        // not be sorted
        else {
          // else we update the last
          // odd element
          odd = A[i];
        }
      }
 
      // if the element is even
      else {
        if (A[i] < even) {
          flag = 0;
          break;
        }
 
        // if it is less than previous
        // even element, then array can
        // not be sorted
        even = A[i];
 
        // else we update
        // the last even element
      }
    }
 
    // all even elements are sorted and all
    // odd elements are sorted, hence we
    // return true as it is possible to
    // sort the array
    if (flag  == 1) {
      return true;
    }
 
    // not possible to sort the array
    return false;
  }
 
  // Driver Code
  public static void main (String[] args) {   
    int n = 4;
    int A[] = { 1, 6, 51, 16 };
    Boolean answer = canBeSorted(n, A);
 
    if (answer == true) {
      System.out.println("YES");
    }
    else {
      System.out.println("NO");
    }
 
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python Code for the Check if array can be
# sorted by swapping adjacent elements
# of opposite parity
 
# function to check if the array can be
# sorted in increasing order by
# swappingadjacent elements of same parity
def canBeSorted(n, A):
 
    # declaring & initializing odd and
    # even variables, that stores previous
    # odd and even elements respectively
    odd = -1
    even = -1
 
    # declaring and initializing flag
    # variable to store the answer
    flag = 1
 
    # iterating through the array
    for i in range(0, n):
        # if the element is odd
        if (A[i] % 2 == 1):
            if (A[i] < odd):
                flag = 0
                break
 
            # if it is less than previous
            # odd element, then array can
            # not be sorted
            else:
                # else we update the last
                # odd element
                odd = A[i]
 
        # if the element is even
        else:
            if (A[i] < even):
                flag = 0
                break
 
            # if it is less than previous
            # even element, then array can
            # not be sorted
            even = A[i]
 
            # else we update
            # the last even element
 
    # all even elements are sorted and all
    # odd elements are sorted, hence we
    # return true as it is possible to
    # sort the array
    if (flag):
        return True
 
    # not possible to sort the array
    return False
 
# Driver Code
n = 4
A = [1, 6, 51, 16]
answer = canBeSorted(n, A)
 
if (answer == 1):
    print("YES")
 
else:
    print("NO")
 
# This code is contributed by Palak Gupta

C#

// C# Code for the Check if array can be
// sorted by swapping adjacent elements
// of opposite parity
using System;
class GFG {
 
  // function to check if the array can be
  // sorted in increasing order by
  // swappingadjacent elements of same parity
  static bool canBeSorted(int n, int []A)
  {
 
    // declaring & initializing odd and
    // even variables, that stores previous
    // odd and even elements respectively
    int odd = -1, even = -1;
 
    // declaring and initializing flag
    // variable to store the answer
    int flag = 1;
 
    // iterating through the array
    for (int i = 0; i < n; i++) {
 
      // if the element is odd
      if (A[i] % 2 == 1) {
        if (A[i] < odd) {
          flag = 0;
          break;
        }
 
        // if it is less than previous
        // odd element, then array can
        // not be sorted
        else {
          // else we update the last
          // odd element
          odd = A[i];
        }
      }
 
      // if the element is even
      else {
        if (A[i] < even) {
          flag = 0;
          break;
        }
 
        // if it is less than previous
        // even element, then array can
        // not be sorted
        even = A[i];
 
        // else we update
        // the last even element
      }
    }
 
    // all even elements are sorted and all
    // odd elements are sorted, hence we
    // return true as it is possible to
    // sort the array
    if (flag  == 1) {
      return true;
    }
 
    // not possible to sort the array
    return false;
  }
 
  // Driver Code
  public static void Main () {   
    int n = 4;
    int []A = { 1, 6, 51, 16 };
    bool answer = canBeSorted(n, A);
 
    if (answer == true) {
      Console.WriteLine("YES");
    }
    else {
      Console.WriteLine("NO");
    }
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
        // JavaScript code for the above approach
 
        // function to check if the array can be
        // sorted in increasing order by
        // swappingadjacent elements of same parity
        function canBeSorted(n, A)
        {
         
            // declaring & initializing odd and
            // even variables, that stores previous
            // odd and even elements respectively
            let odd = -1, even = -1;
 
            // declaring and initializing flag
            // variable to store the answer
            let flag = 1;
 
            // iterating through the array
            for (let i = 0; i < n; i++) {
 
                // if the element is odd
                if (A[i] % 2 == 1) {
                    if (A[i] < odd) {
                        flag = 0;
                        break;
                    }
 
                    // if it is less than previous
                    // odd element, then array can
                    // not be sorted
                    else
                    {
                     
                        // else we update the last
                        // odd element
                        odd = A[i];
                    }
                }
 
                // if the element is even
                else {
                    if (A[i] < even) {
                        flag = 0;
                        break;
                    }
 
                    // if it is less than previous
                    // even element, then array can
                    // not be sorted
                    even = A[i];
 
                    // else we update
                    // the last even element
                }
            }
 
            // all even elements are sorted and all
            // odd elements are sorted, hence we
            // return true as it is possible to
            // sort the array
            if (flag) {
                return true;
            }
 
            // not possible to sort the array
            return false;
        }
 
        // Driver Code
        let n = 4;
        let A = [1, 6, 51, 16];
        let answer = canBeSorted(n, A);
 
        if (answer == 1) {
            document.write("YES");
        }
        else {
            document.write("NO");
        }
 
       // This code is contributed by Potta Lokesh
    </script>
Producción

YES

Complejidad de tiempo: O(n), donde n es el tamaño de la array
Espacio auxiliar:   O(1), ya que no se utiliza espacio adicional

Publicación traducida automáticamente

Artículo escrito por kamabokogonpachiro 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 *