Programa Php para reorganizar una array tal que arr[i] >= arr[j] si i es par y arr[i]<=arr[j] si i es impar y j < i

Dada una array de n elementos. Nuestra tarea es escribir un programa para reorganizar el arreglo de modo que los elementos en las posiciones pares sean mayores que todos los elementos anteriores y los elementos en las posiciones impares sean menores que todos los elementos anteriores.
Ejemplos: 
 

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

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

La idea para resolver este problema es crear primero una copia auxiliar de la array original y ordenar la array copiada. Ahora el número total de posiciones pares en la array con n elementos será piso (n/2) y el resto es el número de posiciones impares. Ahora llene las posiciones pares e impares en la array original usando la array ordenada de la siguiente manera: 
 

• El total de posiciones impares será n – piso (n/2). Comience desde (n-piso (n/2)) la posición en la array ordenada y copie el elemento en la primera posición de la array ordenada. Comience a recorrer la array ordenada desde esta posición hacia la izquierda y siga llenando las posiciones impares en la array original hacia la derecha.
• Comience a recorrer la array ordenada a partir de (n-piso (n/2) + 1) ª posición hacia la derecha y siga llenando la array original a partir de la segunda posición. 
   

A continuación se muestra la implementación de la idea anterior: 
 

<?php
// PHP program to rearrange the array
// as per the given condition
 
// function to rearrange the array
function rearrangeArr(&$arr, $n)
{
    // total even positions
    $evenPos = intval($n / 2);
 
    // total odd positions
    $oddPos = $n - $evenPos;
 
    $tempArr = array_fill(0, $n, NULL);
 
    // copy original array in an
    // auxiliary array
    for ($i = 0; $i < $n; $i++)
        $tempArr[$i] = $arr[$i];
 
    // sort the auxiliary array
    sort($tempArr);
 
    $j = $oddPos - 1;
 
    // fill up odd position in
    // original array
    for ($i = 0; $i < $n; $i += 2)
    {
        $arr[$i] = $tempArr[$j];
        $j--;
    }
 
    $j = $oddPos;
 
    // fill up even positions in
    // original array
    for ($i = 1; $i < $n; $i += 2)
    {
        $arr[$i] = $tempArr[$j];
        $j++;
    }
 
    // display array
    for ($i = 0; $i < $n; $i++)
        echo $arr[$i] ." ";
}
 
// Driver code
$arr = array(1, 2, 3, 4, 5, 6, 7 );
$size = sizeof($arr);
rearrangeArr($arr, $size);
 
// This code is contributed
// by ChitraNayal
?>

Producción: 
 

4 5 3 6 2 7 1

Complejidad de tiempo: O(N*logN), ya que estamos usando una función de clasificación.

Espacio Auxiliar: O(N), ya que estamos usando espacio extra.

Consulte el artículo completo sobre Reorganizar array de manera que arr[i] >= arr[j] si i es par y arr[i]<=arr[j] si i es impar yj <i para obtener más detalles.