Ordenar los elementos pares en orden creciente y los impares en orden decreciente

Nos dan una array de n números distintos. La tarea es clasificar todos los números pares en orden creciente y los números impares en orden decreciente. La array modificada debe contener todos los números pares ordenados seguidos de los números impares ordenados inversamente.

Tenga en cuenta que el primer elemento se considera incluso colocado debido a su índice 0. 

Ejemplos:  

Input:  arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
Output: arr[] = {0, 2, 4, 6, 7, 5, 3, 1}
Even-place elements : 0, 2, 4, 6
Odd-place elements : 1, 3, 5, 7
Even-place elements in increasing order : 
0, 2, 4, 6
Odd-Place elements in decreasing order : 
7, 5, 3, 1

Input: arr[] = {3, 1, 2, 4, 5, 9, 13, 14, 12}
Output: {2, 3, 5, 12, 13, 14, 9, 4, 1}
Even-place elements : 3, 2, 5, 13, 12
Odd-place elements : 1, 4, 9, 14
Even-place elements in increasing order : 
2, 3, 5, 12, 13
Odd-Place elements in decreasing order : 
14, 9, 4, 1 

La idea es sencilla. Creamos dos arreglos auxiliares evenArr[] y oddArr[] respectivamente. Atravesamos la array de entrada y colocamos todos los elementos colocados pares en evenArr[] y los elementos impares colocados en oddArr[]. Luego ordenamos evenArr[] en orden ascendente y oddArr[] en orden descendente. Finalmente, copie evenArr[] y oddArr[] para obtener el resultado requerido.

Implementación:

// Program to separately sort even-placed and odd
// placed numbers and place them together in sorted
// array.
#include <bits/stdc++.h>
using namespace std;
 
void bitonicGenerator(int arr[], int n)
{
    // create evenArr[] and oddArr[]
    vector<int> evenArr;
    vector<int> oddArr;
 
    // Put elements in oddArr[] and evenArr[] as
    // per their position
    for (int i = 0; i < n; i++) {
        if (!(i % 2))
            evenArr.push_back(arr[i]);
        else
            oddArr.push_back(arr[i]);
    }
 
    // sort evenArr[] in ascending order
    // sort oddArr[] in descending order
    sort(evenArr.begin(), evenArr.end());
    sort(oddArr.begin(), oddArr.end(), greater<int>());
 
    int i = 0;
    for (int j = 0; j < evenArr.size(); j++)
        arr[i++] = evenArr[j];
    for (int j = 0; j < oddArr.size(); j++)
        arr[i++] = oddArr[j];
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bitonicGenerator(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

// Java Program to separately sort
// even-placed and odd placed numbers
// and place them together in sorted
// array.
import java.util.*;
 
class GFG {
 
    static void bitonicGenerator(int arr[], int n)
    {
        // create evenArr[] and oddArr[]
        Vector<Integer> evenArr = new Vector<Integer>();
        Vector<Integer> oddArr = new Vector<Integer>();
 
        // Put elements in oddArr[] and evenArr[] as
        // per their position
        for (int i = 0; i < n; i++) {
            if (i % 2 != 1) {
                evenArr.add(arr[i]);
            }
            else {
                oddArr.add(arr[i]);
            }
        }
 
        // sort evenArr[] in ascending order
        // sort oddArr[] in descending order
        Collections.sort(evenArr);
        Collections.sort(oddArr, Collections.reverseOrder());
 
        int i = 0;
        for (int j = 0; j < evenArr.size(); j++) {
            arr[i++] = evenArr.get(j);
        }
        for (int j = 0; j < oddArr.size(); j++) {
            arr[i++] = oddArr.get(j);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
        int n = arr.length;
        bitonicGenerator(arr, n);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program to separately sort
# even-placed and odd placed numbers
# and place them together in sorted array.
def bitonicGenerator(arr, n):
     
    # create evenArr[] and oddArr[]
    evenArr = []
    oddArr = []
 
    # Put elements in oddArr[] and evenArr[]
    # as per their position
    for i in range(n):
        if ((i % 2) == 0):
            evenArr.append(arr[i])
        else:
            oddArr.append(arr[i])
 
    # sort evenArr[] in ascending order
    # sort oddArr[] in descending order
    evenArr = sorted(evenArr)
    oddArr = sorted(oddArr)
    oddArr = oddArr[::-1]
 
    i = 0
    for j in range(len(evenArr)):
        arr[i] = evenArr[j]
        i += 1
    for j in range(len(oddArr)):
        arr[i] = oddArr[j]
        i += 1
 
# Driver Code
arr = [1, 5, 8, 9, 6, 7, 3, 4, 2, 0]
n = len(arr)
bitonicGenerator(arr, n)
for i in arr:
    print(i, end = " ")
 
# This code is contributed by Mohit Kumar

// C# Program to separately sort
// even-placed and odd placed numbers
// and place them together in sorted
// array.
using System;
using System.Collections.Generic;
 
class GFG
{
 
    static void bitonicGenerator(int []arr, int n)
    {
        // create evenArr[] and oddArr[]
        List<int> evenArr = new List<int>();
        List<int> oddArr = new List<int>();
        int i = 0;
         
        // Put elements in oddArr[] and evenArr[] as
        // per their position
        for (i = 0; i < n; i++)
        {
            if (i % 2 != 1)
            {
                evenArr.Add(arr[i]);
            }
            else
            {
                oddArr.Add(arr[i]);
            }
        }
 
        // sort evenArr[] in ascending order
        // sort oddArr[] in descending order
        evenArr.Sort();
        oddArr.Sort();
        oddArr.Reverse();
 
        i = 0;
        for (int j = 0; j < evenArr.Count; j++)
        {
            arr[i++] = evenArr[j];
        }
        for (int j = 0; j < oddArr.Count; j++)
        {
            arr[i++] = oddArr[j];
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
        int n = arr.Length;
        bitonicGenerator(arr, n);
        for (int i = 0; i < n; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
}
 
// This code contributed by Rajput-Ji

<script>
// Javascript Program to separately sort
// even-placed and odd placed numbers
// and place them together in sorted
// array.
     
    function bitonicGenerator(arr,n)
    {
        // create evenArr[] and oddArr[]
        let evenArr = [];
        let oddArr = [];
   
        // Put elements in oddArr[] and evenArr[] as
        // per their position
        for (let i = 0; i < n; i++) {
            if (i % 2 != 1) {
                evenArr.push(arr[i]);
            }
            else {
                oddArr.push(arr[i]);
            }
        }
   
        // sort evenArr[] in ascending order
        // sort oddArr[] in descending order
        evenArr.sort(function(a,b){return a-b;});
        oddArr.sort(function(a,b){return b-a;});
   
        let i = 0;
        for (let j = 0; j < evenArr.length; j++) {
            arr[i++] = evenArr[j];
        }
        for (let j = 0; j < oddArr.length; j++) {
            arr[i++] = oddArr[j];
        }
    }
     
     // Driver code
    let arr=[1, 5, 8, 9, 6, 7, 3, 4, 2, 0 ];
    let  n = arr.length;
    bitonicGenerator(arr, n);
    for (let i = 0; i < n; i++) {
        document.write(arr[i] + " ");
    }
     
    // This code is contributed by unknown2108
</script>

1 2 3 6 8 9 7 5 4 0 

Complejidad de tiempo: O(n Log n) 
Complejidad de espacio: O(n)

El problema anterior también se puede resolver sin el uso del espacio auxiliar. La idea es intercambiar las posiciones de índice impares de la primera mitad con las posiciones de índice pares de la segunda mitad y luego ordenar la array de la primera mitad en orden creciente y la array de la segunda mitad en orden decreciente. Gracias a SWARUPANANDA DHUA por sugerir esto.

Implementación:

// Program to sort even-placed elements in increasing and
// odd-placed in decreasing order with constant space complexity
 
#include <bits/stdc++.h>
using namespace std;
 
void bitonicGenerator(int arr[], int n)
{
    // first odd index
    int i = 1;
 
    // last index
    int j = n - 1;
 
    // if last index is odd
    if (j % 2 != 0)
        // decrement j to even index
        j--;
 
    // swapping till half of array
    while (i < j) {
        swap(arr[i], arr[j]);
        i += 2;
        j -= 2;
    }
 
    // Sort first half in increasing
    sort(arr, arr + (n + 1) / 2);
 
    // Sort second half in decreasing
    sort(arr + (n + 1) / 2, arr + n, greater<int>());
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bitonicGenerator(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
// This code is contributed by SWARUPANANDA DHUA

// Program to sort even-placed elements in increasing and
// odd-placed in decreasing order with constant space complexity
import java.util.Arrays;
class GFG {
 
    static void bitonicGenerator(int arr[], int n)
    {
        // first odd index
        int i = 1;
 
        // last index
        int j = n - 1;
 
        // if last index is odd
        if (j % 2 != 0)
            // decrement j to even index
            j--;
 
        // swapping till half of array
        while (i < j) {
            arr = swap(arr, i, j);
            i += 2;
            j -= 2;
        }
 
        // Sort first half in increasing
        Arrays.sort(arr, 0, (n + 1) / 2);
 
        // Sort second half in decreasing
        Arrays.sort(arr, (n + 1) / 2, n);
        int low = (n + 1) / 2, high = n - 1;
        // Reverse the second half
        while (low < high) {
            Integer temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++;
            high--;
        }
    }
    static int[] swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
    // Driver Program
    public static void main(String[] args)
    {
        int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
        int n = arr.length;
        bitonicGenerator(arr, n);
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}
// This code has been contributed by 29AjayKumar

# Python3 Program to sort even-placed elements in increasing and
# odd-placed in decreasing order with constant space complexity
def bitonicGenerator(arr, n):
 
    # first odd index
    i = 1
 
    # last index
    j = n - 1
     
    # if last index is odd
    if (j % 2 != 0):
         
        # decrement j to even index
        j = j - 1
         
    # swapping till half of array
    while (i < j) :
        arr[j], arr[i] = arr[i], arr[j]
        i = i + 2
        j = j - 2
         
    arr_f = []
    arr_s = []
     
    for i in range(int((n + 1) / 2)) :
        arr_f.append(arr[i])
     
    i = int((n + 1) / 2)
    while( i < n ) :
        arr_s.append(arr[i])
        i = i + 1
     
    # Sort first half in increasing
    arr_f.sort()
 
    # Sort second half in decreasing
    arr_s.sort(reverse = True)
     
    for i in arr_s:
        arr_f.append(i)
     
    return arr_f
 
# Driver Program
arr = [ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0]
n = len(arr)
arr = bitonicGenerator(arr, n)
print(arr)
 
# This code is contributed by Arnab Kundu

// Program to sort even-placed elements in
// increasing and odd-placed in decreasing order
// with constant space complexity
using System;
     
class GFG
{
    static void bitonicGenerator(int []arr, int n)
    {
        // first odd index
        int i = 1;
 
        // last index
        int j = n - 1;
 
        // if last index is odd
        if (j % 2 != 0)
         
            // decrement j to even index
            j--;
 
        // swapping till half of array
        while (i < j)
        {
            arr = swap(arr, i, j);
            i += 2;
            j -= 2;
        }
 
        // Sort first half in increasing
        Array.Sort(arr, 0, (n + 1) / 2);
 
        // Sort second half in decreasing
        Array.Sort(arr, (n + 1) / 2,
                   n - ((n + 1) / 2));
        int low = (n + 1) / 2, high = n - 1;
         
        // Reverse the second half
        while (low < high)
        {
            int temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++;
            high--;
        }
    }
     
    static int[] swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        int []arr = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
        int n = arr.Length;
        bitonicGenerator(arr, n);
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
// Program to sort even-placed elements in increasing and
// odd-placed in decreasing order with constant space complexity
function bitonicGenerator(arr, n)
{
 
    // first odd index
        let i = 1;
  
        // last index
        let j = n - 1;
  
        // if last index is odd
        if (j % 2 != 0)
            // decrement j to even index
            j--;
  
        // swapping till half of array
        while (i < j) {
            arr = swap(arr, i, j);
            i += 2;
            j -= 2;
        }
         
        // Sort first half in increasing
        // Sort second half in decreasing
        let temp1 = arr.slice(0,Math.floor((n+1)/2)).sort(function(a,b){return a-b;});
        let temp2 = arr.slice(Math.floor((n+1)/2),n).sort(function(a,b){return b-a;});
        arr = temp1.concat(temp2);
            
        return arr;
}
 
function swap(arr, i, j)
{
    let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
}
 
// Driver Program
let arr = [1, 5, 8, 9, 6, 7, 3, 4, 2, 0 ];
let n = arr.length;
arr = bitonicGenerator(arr, n);
document.write(arr.join(" "));
 
// This code is contributed by rag2127
</script>

1 2 3 6 8 9 7 5 4 0 

Complejidad de tiempo: O(n Log n) 
Complejidad de espacio: O(1)

Otro enfoque:
Otro enfoque eficiente para resolver el problema en el espacio auxiliar O(1) es mediante el uso de la multiplicación negativa .

Los pasos involucrados son los siguientes:

1.  Multiplique todos los elementos en el índice incluso colocado por -1.
2. Ordenar toda la array. De esta manera, podemos obtener todos los índices incluso colocados al principio, ya que ahora son números negativos.
3. Ahora invierte el signo de estos elementos.
4. Después de esto, invierta la primera mitad de la array que contiene un número par para hacerlo en orden creciente.
5. Y luego invierta la mitad restante de la array para hacer números impares en orden decreciente.

Nota: este método solo es aplicable si todos los elementos de la array no son negativos.

Un ejemplo ilustrativo del enfoque anterior:

Deje array dada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
Array después de multiplicar por -1 para elementos incluso colocados: arr[] = {0, 1, -2, 3, -4, 5, -6, 7}
Array después de ordenar: arr[] = {-6, -4, -2, 0, 1, 3, 5, 7}
Array después de revertir valores negativos: arr[] = {6 , 4, 2, 0, 1, 3, 5, 7}
Después de invertir la primera mitad de la array: arr[] = {0, 2, 4, 6, 1, 3, 5, 7}
Después de invertir la segunda mitad de array: array[] = {0, 2, 4, 6, 7, 5, 3, 1}

A continuación se muestra el código para el enfoque anterior:

// C++ Program to sort even-placed elements in increasing and
// odd-placed in decreasing order with constant space complexity
#include <bits/stdc++.h>
using namespace std;
 
void bitonicGenerator(int arr[], int n)
{
    // Making all even placed index
    // element negative
    for (int i = 0; i < n; i++) {
        if (i % 2==0)
            arr[i]=-1*arr[i];
    }
     
    // Sorting the whole array
    sort(arr,arr+n);
     
    // Finding the middle value of
    // the array
    int mid=(n-1)/2;
     
    // Reverting the changed sign
    for (int i = 0; i <= mid; i++) {
            arr[i]=-1*arr[i];
    }
     
    // Reverse first half of array
    reverse(arr,arr+mid+1);
    // Reverse second half of array
    reverse(arr+mid+1,arr+n);
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bitonicGenerator(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
 
// This code is contributed by Pushpesh Raj.

// Java Program to sort even-placed elements in increasing and
// odd-placed in decreasing order with constant space complexity
import java.util.Arrays;
 
public class GFG {
 
static void reverse(int a[], int l,int r)
{
    while(l<=r)
    {
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
        l++;
        r--;
    }
}
 
 
static void bitonicGenerator(int[] arr, int n)
{
    // Making all even placed index
    // element negative
    for (int i = 0; i < n; i++) {
        if (i % 2==0)
            arr[i]=-1*arr[i];
    }
      
    // Sorting the whole array
    Arrays.sort(arr);
      
    // Finding the middle value of
    // the array
    int mid=(n-1)/2;
      
    // Reverting the changed sign
    for (int i = 0; i <= mid; i++) {
            arr[i]=-1*arr[i];
    }
      
    // Reverse first half of array
    reverse(arr,0,mid);
    // Reverse second half of array
    reverse(arr,mid+1,n-1);
     
}
  
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
        int n = arr.length;
        bitonicGenerator(arr, n);
        for (int i = 0; i < n; i++)
        System.out.print(arr[i]+" ");
    }
}
// This code is contributed by aditya942003patil

1 2 3 6 8 9 7 5 4 0 

Complejidad de tiempo: O(n*log(n)) 
Complejidad de espacio: O(1)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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.