Programa de Python3 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: 
 

# Python3 code to rearrange the array
# as per the given condition
import array as a
import numpy as np
 
# function to rearrange the array
def rearrangeArr(arr, n):
     
    # total even positions
    evenPos = int(n / 2)
 
    # total odd positions
    oddPos = n - evenPos
 
    # initialising empty array in python
    tempArr = np.empty(n, dtype = object)
 
    # copy original array in an
    # auxiliary array
    for i in range(0, n):
         
        tempArr[i] = arr[i]
 
    # sort the auxiliary array
    tempArr.sort()
 
    j = oddPos - 1
 
    # fill up odd position in original
    # array
    for i in range(0, n, 2):
 
        arr[i] = tempArr[j]
        j = j - 1
     
    j = oddPos
 
    # fill up even positions in original
    # array
    for i in range(1, n, 2):
        arr[i] = tempArr[j]
        j = j + 1
     
    # display array
    for i in range(0, n):
        print (arr[i], end = ' ')
 
# Driver code
arr = a.array('i', [ 1, 2, 3, 4, 5, 6, 7 ])
rearrangeArr(arr, 7)
 
# This code is contributed by saloni1297

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.