Programa en C++ para reorganizar un arreglo 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: 
 

// C++ program to rearrange the array
// as per the given condition
 
#include <bits/stdc++.h>
using namespace std;
 
// function to rearrange the array
void rearrangeArr(int arr[], int n)
{
    // total even positions
    int evenPos = n / 2;
 
    // total odd positions
    int oddPos = n - evenPos;
 
    int tempArr[n];
 
    // copy original array in an
    // auxiliary array
    for (int i = 0; i < n; i++)
        tempArr[i] = arr[i];
 
    // sort the auxiliary array
    sort(tempArr, tempArr + n);
 
    int j = oddPos - 1;
 
    // fill up odd position in original
    // array
    for (int i = 0; i < n; i += 2) {
        arr[i] = tempArr[j];
        j--;
    }
 
    j = oddPos;
 
    // fill up even positions in original
    // array
    for (int i = 1; i < n; i += 2) {
        arr[i] = tempArr[j];
        j++;
    }
 
    // display array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    rearrangeArr(arr, size);
    return 0;
}

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.