Reorganice la array de modo que los elementos de índice pares sean más pequeños y los elementos de índice impares sean más grandes

Dada una array, reorganice la array de manera que: 

1. Si el índice i es par, arr[i] <= arr[i+1]
2. Si el índice i es impar, arr[i] >= arr[i+1]

Nota: Puede haber múltiples respuestas.

Ejemplos:  

Input  : arr[] = {2, 3, 4, 5} 
Output : arr[] = {2, 4, 3, 5}
Explanation : Elements at even indexes are
smaller and elements at odd indexes are greater
than their next elements

Note : Another valid answer
is arr[] = {3, 4, 2, 5}

Input  :arr[] = {6, 4, 2, 1, 8, 3}
Output :arr[] = {4, 6, 1, 8, 2, 3}

Este problema es similar a clasificar una array en la forma de onda .

• Una solución simple es ordenar la array en orden decreciente y luego, a partir del segundo elemento, intercambiar los elementos adyacentes.
• Una solución eficiente es iterar sobre la array e intercambiar los elementos según la condición dada. 

Si tenemos una array de longitud n, iteramos desde el índice 0 hasta n-2 y verificamos la condición dada. 
En cualquier momento, si i es par y arr[i] > arr[i+1], entonces intercambiamos arr[i] y arr[i+1]. De manera similar, si i es impar y 
arr[i] < arr[i+1], entonces intercambiamos arr[i] y arr[i+1].
Para el ejemplo dado: 

Before rearrange, arr[] = {2, 3, 4, 5} 
Start iterating over the array till index 2 (as n = 4) 

Primer paso: 
en i = 0, arr[i] = 2 y arr[i+1] = 3. Como i es par y arr[i] < arr[i+1], no es necesario cambiar. 
Segundo paso: 
en i = 1, arr[i] = 3 y arr[i+1] = 4. Como i es impar y arr[i] < arr[i+1], cámbielos. 
Ahora arr[] = {2, 4, 3, 5} 
Tercer paso: 
En i = 2, arr[i] = 3 y arr[i+1] = 5. Entonces, no es necesario cambiarlos

Después de reorganizar, arr[] = {2, 4, 3, 5} 

diagrama de flujo

diagrama de flujo

Implementación:

// CPP code to rearrange an array such that
// even index elements are smaller and odd
// index elements are greater than their
// next.
#include <iostream>
using namespace std;
 
void rearrange(int* arr, int n)
{
    for (int i = 0; i < n - 1; i++) {
        if (i % 2 == 0 && arr[i] > arr[i + 1])
            swap(arr[i], arr[i + 1]);
 
        if (i % 2 != 0 && arr[i] < arr[i + 1])
            swap(arr[i], arr[i + 1]);
    }
}
 
/* Utility that prints out an array in
   a line */
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
 
    cout << endl;
}
 
/* Driver function to test above functions */
int main()
{
    int arr[] = { 6, 4, 2, 1, 8, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Before rearranging: \n";
    printArray(arr, n);
 
    rearrange(arr, n);
 
    cout << "After rearranging: \n";
    printArray(arr, n);
 
    return 0;
}

// Java code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
 
class GFG {
 
    static void rearrange(int arr[], int n)
    {
 
        int temp;
        for (int i = 0; i < n - 1; i++) {
            if (i % 2 == 0 && arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
            if (i % 2 != 0 && arr[i] < arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
 
    /* Utility that prints out an array in
    a line */
    static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
 
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 6, 4, 2, 1, 8, 3 };
        int n = arr.length;
 
        System.out.print("Before rearranging: \n");
        printArray(arr, n);
 
        rearrange(arr, n);
 
        System.out.print("After rearranging: \n");
        printArray(arr, n);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python code to rearrange
# an array such that
# even index elements
# are smaller and odd
# index elements are
# greater than their
# next.
 
def rearrange(arr, n):
 
    for i in range(n - 1):
        if (i % 2 == 0 and arr[i] > arr[i + 1]):
         
            temp = arr[i]
            arr[i]= arr[i + 1]
            arr[i + 1]= temp
         
        if (i % 2 != 0 and arr[i] < arr[i + 1]):
          
            temp = arr[i]
            arr[i]= arr[i + 1]
            arr[i + 1]= temp
            
  
# Utility that prints out an array in
# a line
def printArray(arr, size):
 
    for i in range(size):
        print(arr[i], " ", end ="")
  
    print()
 
# Driver code
 
arr = [ 6, 4, 2, 1, 8, 3 ]
n = len(arr)
  
print("Before rearranging: ")
printArray(arr, n)
  
rearrange(arr, n)
  
print("After rearranging:")
printArray(arr, n);
 
# This code is contributed
# by Anant Agarwal.

// C# code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
using System;
 
class GFG {
 
    static void rearrange(int[] arr, int n)
    {
        int temp;
        for (int i = 0; i < n - 1; i++) {
            if (i % 2 == 0 && arr[i] > arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
             
            if (i % 2 != 0 && arr[i] < arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
 
    /* Utility that prints out an array in
    a line */
    static void printArray(int[] arr, int size)
    {
        for (int i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
 
        Console.WriteLine();
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 6, 4, 2, 1, 8, 3 };
        int n = arr.Length;
 
        Console.WriteLine("Before rearranging: ");
        printArray(arr, n);
 
        rearrange(arr, n);
 
        Console.WriteLine("After rearranging: ");
        printArray(arr, n);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to rearrange an array such
// that even index elements are smaller
// and odd index elements are greater
// than their next.
 
function swap(&$a, &$b)
{
    $temp = $a;
    $a = $b;
    $b = $temp;
}
function rearrange(&$arr, $n)
{
    for ($i = 0; $i < $n - 1; $i++)
    {
        if ($i % 2 == 0 &&
            $arr[$i] > $arr[$i + 1])
            swap($arr[$i], $arr[$i + 1]);
 
        if ($i % 2 != 0 &&
            $arr[$i] < $arr[$i + 1])
            swap($arr[$i], $arr[$i + 1]);
    }
}
 
/* Utility that prints out
an array in a line */
function printArray(&$arr, $size)
{
    for ($i = 0; $i < $size; $i++)
        echo $arr[$i] . " ";
 
    echo "\n";
}
 
// Driver Code
$arr = array(6, 4, 2, 1, 8, 3 );
$n = sizeof($arr);
 
echo "Before rearranging: \n";
printArray($arr, $n);
 
rearrange($arr, $n);
 
echo "After rearranging: \n";
printArray($arr, $n);
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
// JavaScript code to rearrange an array such that
// even index elements are smaller and odd
// index elements are greater than their
// next.
 
let rearrange = (arr, n)=>{
    for (let i = 0; i < n - 1; i++) {
        if (i % 2 == 0 && arr[i] > arr[i + 1]){
            // swap(arr[i], arr[i + 1]);
            let temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
        if (i % 2 != 0 && arr[i] < arr[i + 1]){
            // swap(arr[i], arr[i + 1]);
            let temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
       }
    }
}
 
// function to print array
let printArray = (arr, size)=>{
    ans = '';
    for (let i = 0; i < size; i++){
        ans += arr[i] + " ";
    }
    document.write(ans);
}
 
// Driver Code
let arr = [ 6, 4, 2, 1, 8, 3 ];
let n = arr.length;
 
document.write("Before rearranging: ");
printArray(arr, n);
rearrange(arr, n);
document.write("<br>");
document.write("After rearranging: ");
printArray(arr, n);
 
</script>

Before rearranging: 
6 4 2 1 8 3 
After rearranging: 
4 6 1 8 2 3 

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.

Este artículo es una contribución de Sukanta Nandi . 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.