Reorganice la array de manera 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 adicional de la array original y ordenar la array copiada. Ahora el número total de posiciones pares en una 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 la posición (n-piso (n/2)) 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 = oddPos;
 
    // fill up even positions in original array
    for (int i = 1; i < n; i += 2)
        arr[i] = tempArr[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;
}

// C program to rearrange the array as per the given
// condition
#include <stdio.h>
#include <stdlib.h>
 
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}
 
// 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
    qsort(tempArr, n, sizeof(int), cmpfunc);
    int j = oddPos - 1;
 
    // fill up odd position in original array
    for (int i = 0; i < n; i += 2)
        arr[i] = tempArr[j--];
 
    j = oddPos;
 
    // fill up even positions in original array
    for (int i = 1; i < n; i += 2)
        arr[i] = tempArr[j++];
 
    // display array
    for (int i = 0; i < n; i++)
        printf("%d ", 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;
}
 
// This code is contributed by Sania Kumari Gupta

// Java program to rearrange the array
// as per the given condition
import java.util.*;
import java.lang.*;
 
public class GfG{
    // function to rearrange the array
    public static void rearrangeArr(int arr[],
                                        int n)
    {
        // total even positions
        int evenPos = n / 2;
 
        // total odd positions
        int oddPos = n - evenPos;
 
        int[] tempArr = new int [n];
 
        // copy original array in an
        // auxiliary array
        for (int i = 0; i < n; i++)
            tempArr[i] = arr[i];
 
        // sort the auxiliary array
        Arrays.sort(tempArr);
 
        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++)
            System.out.print(arr[i] + " ");
    }
     
    // Driver function
    public static void main(String argc[]){
        int[] arr = new int []{ 1, 2, 3, 4, 5,
                                        6, 7 };
        int size = 7;
        rearrangeArr(arr, size);
         
    }
}
 
/* This code is contributed by Sagar Shukla */

# 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

// C# program to rearrange the array
// as per the given condition
using System;
 
public class GfG {
     
    // Function to rearrange the array
    public static void rearrangeArr(int []arr, int n)
    {
        // total even positions
        int evenPos = n / 2;
 
        // total odd positions
        int oddPos = n - evenPos;
 
        int[] tempArr = new int [n];
 
        // copy original array in an
        // auxiliary array
        for (int i = 0; i < n; i++)
            tempArr[i] = arr[i];
 
        // sort the auxiliary array
        Array.Sort(tempArr);
 
        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++)
            Console.Write(arr[i] + " ");
    }
     
    // Driver Code
    public static void Main()
    {
        int[] arr = new int []{ 1, 2, 3, 4, 5, 6, 7 };
        int size = 7;
        rearrangeArr(arr, size);
    }
}
 
/* This code is contributed by vt_m */

<?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
?>

<script>
 
 
// Javascript program to rearrange the array
// as per the given condition
 
 
// function to rearrange the array
function rearrangeArr(arr, n)
{
    // total even positions
    let evenPos = Math.floor(n / 2);
 
    // total odd positions
    let oddPos = n - evenPos;
 
    let tempArr = new Array(n);
 
    // copy original array in an
    // auxiliary array
    for (let i = 0; i < n; i++)
        tempArr[i] = arr[i];
 
    // sort the auxiliary array
    tempArr.sort();
 
    let j = oddPos - 1;
 
    // fill up odd position in original
    // array
    for (let i = 0; i < n; i += 2) {
        arr[i] = tempArr[j];
        j--;
    }
 
    j = oddPos;
 
    // fill up even positions in original
    // array
    for (let i = 1; i < n; i += 2) {
        arr[i] = tempArr[j];
        j++;
    }
 
    // display array
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
}
 
// Driver code
 
    let arr = [ 1, 2, 3, 4, 5, 6, 7 ];
    let size = arr.length;
    rearrangeArr(arr, size);
    
 
//This code is contributed by Mayank Tyagi
</script>

4 5 3 6 2 7 1 

Complejidad de tiempo : O( n logn ) 
Espacio auxiliar : O(n)

Otro enfoque-

Podemos recorrer la array definiendo dos variables p y q y asignar valores desde el último.

si incluso el índice está allí, le daremos el valor máximo, de lo contrario, el valor mínimo.

p =0 y q= fin;

p seguirá adelante y q disminuirá.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n,i,j,p,q;
    int a[]= {1, 2, 1, 4, 5, 6, 8, 8};
    n=sizeof(a)/sizeof(a[0]);
    int b[n];
    for(i=0;i<n;i++)
        b[i]=a[i];
 
    sort(b,b+n);
    p=0;q=n-1;
    for(i=n-1;i>=0;i--){
            if(i%2!=0){
            a[i]=b[q];
            q--;
            }
            else{
                a[i]=b[p];
                p++;
            }
    }
    for(i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

import java.util.*;
 
class GFG{
 
  public static void main(String[] args)
  {
    int n, i, j, p, q;
    int a[] = {1, 2, 1, 4, 5, 6, 8, 8};
    n = a.length;
    int []b = new int[n];
    for(i = 0; i < n; i++)
      b[i] = a[i];
 
    Arrays.sort(b);
    p = 0; q = n - 1;
    for(i = n - 1; i >= 0; i--)
    {
      if(i % 2 != 0)
      {
        a[i] = b[q];
        q--;
      }
      else{
        a[i] = b[p];
        p++;
      }
    }
    for(i = 0; i < n; i++)
    {
      System.out.print(a[i]+" ");
    }
  }
}
 
// This code is contributed by gauravrajput1

if __name__ == '__main__':
    #n, i, j, p, q;
    a = [ 1, 2, 1, 4, 5, 6, 8, 8 ];
    n = len(a);
    b = [0]*n;
    for i in range(n):
        b[i] = a[i];
 
    b.sort();
    p = 0;
    q = n - 1;
    for i in range(n-1, -1,-1):
        if (i % 2 != 0):
            a[i] = b[q];
            q -= 1;
        else:
            a[i] = b[p];
            p += 1;
         
    for i in range(n):
        print(a[i], end=" ");
     
# This code is contributed by gauravrajput1

using System;
 
 
public class GFG{
 
  public static void Main(String[] args)
  {
    int n, i, j, p, q;
    int []a = {1, 2, 1, 4, 5, 6, 8, 8};
    n = a.Length;
    int []b = new int[n];
    for(i = 0; i < n; i++)
      b[i] = a[i];
 
    Array.Sort(b);
    p = 0; q = n - 1;
    for(i = n - 1; i >= 0; i--)
    {
      if(i % 2 != 0)
      {
        a[i] = b[q];
        q--;
      }
      else{
        a[i] = b[p];
        p++;
      }
    }
    for(i = 0; i < n; i++)
    {
      Console.Write(a[i]+" ");
    }
  }
}
 
// This code is contributed by gauravrajput1

<script>
     
        var n, i, j, p, q;
        var a = [ 1, 2, 1, 4, 5, 6, 8, 8 ];
        n = a.length;
        var b = Array(n).fill(0);
        for (i = 0; i < n; i++)
            b[i] = a[i];
 
        b.sort();
        p = 0;
        q = n - 1;
        for (i = n - 1; i >= 0; i--) {
            if (i % 2 != 0) {
                a[i] = b[q];
                q--;
            } else {
                a[i] = b[p];
                p++;
            }
        }
        for (i = 0; i < n; i++) {
            document.write(a[i] + " ");
        }
 
// This code is contributed by gauravrajput1
</script>

4 5 2 6 1 8 1 8 

Complejidad de tiempo: O (nlogn)

Se toma el tiempo máximo para ordenar la array.

Espacio Auxiliar: O(n)

El espacio adicional es necesario para almacenar la copia de los elementos de la array original.

Este algoritmo tomará 1 for loop menos que el anterior.