Dada una array arr[] de tamaño N , la tarea es verificar si es posible ordenar la array mediante las siguientes operaciones:
- Swap(arr[i], arr[j]) , si i & 1 = 1 y j & 1 = 1 .
- Swap(arr[i], arr[j]) , si i & 1 = 0 y j & 1 = 0 .
Ejemplos:
Entrada: arr[] = {3, 5, 1, 2, 6}
Salida: Sí
Explicación:
Intercambiar (3, 1) –> {1, 5, 3, 2, 6}
Intercambiar (5, 2) –> { 1, 2, 3, 5, 6}Entrada: arr[] = {3, 1, 5, 2, 6}
Salida: No
Enfoque ingenuo: la idea es encontrar el elemento mínimo para los índices pares o impares e intercambiarlo del elemento actual si el índice del elemento actual es par o impar respectivamente.
- Recorra la array arr[] y realice las siguientes operaciones:
- Si el índice actual es par, recorre los índices pares restantes.
- Encuentre el elemento mínimo presente en los elementos indexados pares.
- Intercambie el mínimo con el elemento de array actual.
- Repita los pasos anteriores para todos los elementos indexados impares también.
- Después de completar las operaciones anteriores, si la array está ordenada, entonces es posible ordenar la array.
- De lo contrario, no es posible ordenar la array.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check if array
// can be sorted or not
bool isSorted(int arr[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to check if given
// array can be sorted or not
bool sortPoss(int arr[], int n)
{
// Traverse the array
for(int i = 0; i < n; i++)
{
int idx = -1;
int minVar = arr[i];
// Traverse remaining elements
// at indices separated by 2
int j = i;
while (j < n)
{
// If current element
// is the minimum
if (arr[j] < minVar)
{
minVar = arr[j];
idx = j;
}
j = j + 2;
}
// If any smaller minimum exists
if (idx != -1)
{
// Swap with current element
swap(arr[i], arr[idx]);
}
}
// If array is sorted
if (isSorted(arr, n))
return true;
// Otherwise
else
return false;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 3, 5, 1, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (sortPoss(arr, n))
cout << "True";
else
cout << "False";
return 0;
}
// This code is contributed by ukasp
Java
class GFG{
// Function to check if array
// can be sorted or not
public static boolean isSorted(int arr[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to check if given
// array can be sorted or not
public static boolean sortPoss(int arr[], int n)
{
// Traverse the array
for(int i = 0; i < n; i++)
{
int idx = -1;
int minVar = arr[i];
// Traverse remaining elements
// at indices separated by 2
int j = i;
while (j < n)
{
// If current element
// is the minimum
if (arr[j] < minVar)
{
minVar = arr[j];
idx = j;
}
j = j + 2;
}
// If any smaller minimum exists
if (idx != -1)
{
// Swap with current element
int t;
t = arr[i];
arr[i] = arr[idx];
arr[idx] = t;
}
}
// If array is sorted
if (isSorted(arr, n))
return true;
// Otherwise
else
return false;
}
// Driver Code
public static void main(String args[])
{
// Given array
int arr[] = { 3, 5, 1, 2, 6 };
int n = arr.length;
if (sortPoss(arr, n))
System.out.println("True");
else
System.out.println("False");
}
}
// This code is contributed by SoumikMondal
Python3
# Function to check if array # can be sorted or not def isSorted(arr): for i in range(len(arr)-1): if arr[i]>arr[i + 1]: return False return True # Function to check if given # array can be sorted or not def sortPoss(arr): # Traverse the array for i in range(len(arr)): idx = -1 minVar = arr[i] # Traverse remaining elements # at indices separated by 2 for j in range(i, len(arr), 2): # If current element # is the minimum if arr[j]<minVar: minVar = arr[j] idx = j # If any smaller minimum exists if idx != -1: # Swap with current element arr[i], arr[idx] = arr[idx], arr[i] # If array is sorted if isSorted(arr): return True # Otherwise else: return False # Driver Code # Given array arr = [ 3, 5, 1, 2, 6 ] print(sortPoss(arr))
C#
using System;
class GFG{
// Function to check if array
// can be sorted or not
public static bool isSorted(int[] arr, int n)
{
for(int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to check if given
// array can be sorted or not
public static bool sortPoss(int[] arr, int n)
{
// Traverse the array
for(int i = 0; i < n; i++)
{
int idx = -1;
int minVar = arr[i];
// Traverse remaining elements
// at indices separated by 2
int j = i;
while (j < n)
{
// If current element
// is the minimum
if (arr[j] < minVar)
{
minVar = arr[j];
idx = j;
}
j = j + 2;
}
// If any smaller minimum exists
if (idx != -1)
{
// Swap with current element
int t;
t = arr[i];
arr[i] = arr[idx];
arr[idx] = t;
}
}
// If array is sorted
if (isSorted(arr, n))
return true;
// Otherwise
else
return false;
}
// Driver code
static public void Main()
{
// Given array
int[] arr = { 3, 5, 1, 2, 6 };
int n = arr.Length;
if (sortPoss(arr, n))
Console.WriteLine("True");
else
Console.WriteLine("False");
}
}
// This code is contributed by offbeat
Javascript
<script>
// Function to check if array
// can be sorted or not
function isSorted(arr , n) {
for (i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to check if given
// array can be sorted or not
function sortPoss(arr , n) {
// Traverse the array
for (i = 0; i < n; i++) {
var idx = -1;
var minVar = arr[i];
// Traverse remaining elements
// at indices separated by 2
var j = i;
while (j < n) {
// If current element
// is the minimum
if (arr[j] < minVar) {
minVar = arr[j];
idx = j;
}
j = j + 2;
}
// If any smaller minimum exists
if (idx != -1) {
// Swap with current element
var t;
t = arr[i];
arr[i] = arr[idx];
arr[idx] = t;
}
}
// If array is sorted
if (isSorted(arr, n))
return true;
// Otherwise
else
return false;
}
// Driver Code
// Given array
var arr = [ 3, 5, 1, 2, 6 ];
var n = arr.length;
if (sortPoss(arr, n))
document.write("True");
else
document.write("False");
// This code contributed by umadevi9616
</script>
Producción:
True
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es comprobar si se utiliza el hecho de que podemos organizar todos los elementos indexados pares e impares de la forma en que queremos utilizar las operaciones de intercambio.
- Inicialice una array, digamos dupArr[] , para almacenar el contenido de la array dada.
- Ordene la array dupArr[] .
- Compruebe si todos los elementos indexados pares en la array original son los mismos que los elementos indexados pares en dupArr[] .
- Si se encuentra que es cierto, entonces la clasificación es posible. De lo contrario, la clasificación no es posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if array can
// be sorted by given operations
bool isEqual(vector<int>&A,vector<int>&B){
if(A.size() != B.size())return false;
for(int i = 0; i < A.size(); i++){
if(A[i] != B[i])return false;
}
return true;
}
bool sortPoss(vector<int>arr){
// Copy contents
// of the array
vector<int>dupArr(arr.begin(),arr.end());
// Sort the duplicate array
sort(dupArr.begin(),dupArr.end());
vector<int>evenOrg;
vector<int>evenSort;
// Traverse the array
for(int i=0;i<arr.size();i+=2){
// Append even-indexed elements
// of the original array
evenOrg.push_back(arr[i]);
// Append even-indexed elements
// of the duplicate array
evenSort.push_back(dupArr[i]);
}
// Sort the even-indexed elements
sort(evenOrg.begin(),evenOrg.end());
sort(evenSort.begin(),evenSort.end());
// Return true if even-indexed
// elements are identical
return isEqual(evenOrg,evenSort);
}
// Driver Code
int main(){
// Given array
vector<int>arr = {3, 5, 1, 2, 6};
cout << sortPoss(arr) << endl;
}
// This code is contributed by shinjanpatra.
Python3
# Python Program to implement # the above approach # Function to check if array can # be sorted by given operations def sortPoss(arr): # Copy contents # of the array dupArr = list(arr) # Sort the duplicate array dupArr.sort() evenOrg = [] evenSort = [] # Traverse the array for i in range(0, len(arr), 2): # Append even-indexed elements # of the original array evenOrg.append(arr[i]) # Append even-indexed elements # of the duplicate array evenSort.append(dupArr[i]) # Sort the even-indexed elements evenOrg.sort() evenSort.sort() # Return true if even-indexed # elements are identical return evenOrg == evenSort # Driver Code # Given array arr = [3, 5, 1, 2, 6] print(sortPoss(arr))
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if array can
// be sorted by given operations
function isEqual(A,B){
if(A.length != B.length)return false;
for(let i = 0; i < A.length; i++){
if(A[i] != B[i])return false;
}
return true;
}
function sortPoss(arr){
// Copy contents
// of the array
let dupArr = arr.slice();
// Sort the duplicate array
dupArr.sort()
let evenOrg = []
let evenSort = []
// Traverse the array
for(let i=0;i<arr.length;i+=2){
// Append even-indexed elements
// of the original array
evenOrg.push(arr[i])
// Append even-indexed elements
// of the duplicate array
evenSort.push(dupArr[i])
}
// Sort the even-indexed elements
evenOrg.sort()
evenSort.sort()
// Return true if even-indexed
// elements are identical
return isEqual(evenOrg,evenSort);
}
// Driver Code
// Given array
let arr = [3, 5, 1, 2, 6]
document.write(sortPoss(arr),"</br>")
// This code is contributed by shinjanpatra.
</script>
Producción:
True
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA