Ordena todos los números pares en orden ascendente y luego ordena todos los números impares en orden descendente

Dada una array de números enteros (tanto pares como impares), ordénelos de tal manera que la primera parte de la array contenga números impares ordenados en orden descendente, el resto contiene números pares ordenados en orden ascendente.
Ejemplos: 

Entrada: arr[] = {1, 2, 3, 5, 4, 7, 10}
Salida: arr[] = {7, 5, 3, 1, 2, 4, 10}

Entrada: arr[] = {0, 4, 5, 3, 7, 2, 1}
Salida: arr[] = {7, 5, 3, 1, 0, 2, 4} 

Método 1 (usando la partición)  

1. Divida la array de entrada de manera que todos los elementos impares se muevan a la izquierda y todos los elementos pares a la derecha. Este paso toma O(n).
2. Una vez que la array esté dividida, ordene las partes izquierda y derecha individualmente. Este paso toma O(n Log n).

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

// C++ program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
#include <bits/stdc++.h>
using namespace std;
 
// To do two way sort. First sort even numbers in
// ascending order, then odd numbers in descending
// order.
void twoWaySort(int arr[], int n)
{
     
    // Current indexes from left and right
    int l = 0, r = n - 1;
 
    // Count of odd numbers
    int k = 0;
 
    while (l < r)
    {
     
        // Find first even number
        // from left side.
        while (arr[l] % 2 != 0)
        {
            l++;
            k++;
        }
 
        // Find first odd number
        // from right side.
        while (arr[r] % 2 == 0 && l < r)
            r--;
 
        // Swap even number present on left and odd
        // number right.
        if (l < r)
            swap(arr[l], arr[r]);
    }
 
    // Sort odd number in descending order
    sort(arr, arr + k, greater<int>());
 
    // Sort even number in ascending order
    sort(arr + k, arr + n);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 7, 5, 4 };
    int n = sizeof(arr) / sizeof(int);
    twoWaySort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

// Java program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
 
import java.util.Arrays;
import java.util.Collections;
 
public class GFG {
    // To do two way sort. First sort even numbers in
    // ascending order, then odd numbers in descending
    // order.
    static void twoWaySort(Integer arr[], int n)
    {
        // Current indexes from left and right
        int l = 0, r = n - 1;
 
        // Count of odd numbers
        int k = 0;
 
        while (l < r)
        {
         
            // Find first even number from left side.
            while (arr[l] % 2 != 0)
            {
                l++;
                k++;
            }
 
            // Find first odd number from right side.
            while (arr[r] % 2 == 0 && l < r)
                r--;
 
            // Swap even number present on left and odd
            // number right.
            if (l < r)
            {
             
                // swap arr[l] arr[r]
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
 
        // Sort odd number in descending order
        Arrays.sort(arr, 0, k, Collections.
                                  reverseOrder());
 
        // Sort even number in ascending order
        Arrays.sort(arr, k, n);
    }
 
    // Driver Method
    public static void main(String[] args)
    {
        Integer arr[] = { 1, 3, 2, 7, 5, 4 };
 
        twoWaySort(arr, arr.length);
 
        System.out.println(Arrays.toString(arr));
    }
}

# Python program to sort array
# in even and odd manner
# The odd numbers are to be
# sorted in descending order
# and the even numbers in
# ascending order
 
# To do two way sort. First
# sort even numbers in ascending
# order, then odd numbers in
# descending order.
def two_way_sort(arr, arr_len):
     
    # Current indexes l->left
    # and r->right
    l, r = 0, arr_len - 1
     
    # Count of number of
    # odd numbers, used in
    # slicing the array later.
    k = 0
     
    # Run till left(l) < right(r)
    while(l < r):
         
        # While left(l) is odd, if yes
        # increment the left(l) plus
        # odd count(k) if not break the
        # while for even number found
        # here to be swapped
        while(arr[l] % 2 != 0):
            l += 1
            k += 1
             
        # While right(r) is even,
        # if yes decrement right(r)
        # if not break the while for
        # odd number found here to
        # be swapped    
        while(arr[r] % 2 == 0 and l < r):
            r -= 1
             
        # Swap the left(l) and right(r),
        # which is even and odd numbers
        # encountered in above loops
        if(l < r):
            arr[l], arr[r] = arr[r], arr[l]
             
    # Slice the number on the
    # basis of odd count(k)
    odd = arr[:k]
    even = arr[k:]
     
    # Sort the odd and
    # even array accordingly
    odd.sort(reverse = True)
    even.sort()
     
    # Extend the odd array with
    # even values and return it.
    odd.extend(even)
     
    return odd
     
# Driver code
arr_len = 6
arr = [1, 3, 2, 7, 5, 4]
result = two_way_sort(arr, arr_len)
for i in result:
    print(str(i) + " "),
 
# This code is contributed
# by JaySiyaRam

// C# program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
using System;
using System.Linq;
 
class GFG {
    // To do two way sort. First sort even numbers in
    // ascending order, then odd numbers in descending
    // order.
    static void twoWaySort(int[] arr, int n)
    {
        // Current indexes from left and right
        int l = 0, r = n - 1;
 
        // Count of odd numbers
        int k = 0;
 
        while (l < r)
        {
         
            // Find first even number
            // from left side.
            while (arr[l] % 2 != 0)
            {
                l++;
                k++;
            }
 
            // Find first odd number from right side.
            while (arr[r] % 2 == 0 && l < r)
                r--;
 
            // Swap even number present
            // on left and odd
            // number right.
            if (l < r) {
                // swap arr[l] arr[r]
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
 
        // Sort odd number in descending order
        Array.Sort(arr, 0, k);
        Array.Reverse(arr, 0, k);
 
        // Sort even number in ascending order
        Array.Sort(arr, k, n - k);
    }
 
    // Driver Method
    public static void Main(String[] args)
    {
        int[] arr = { 1, 3, 2, 7, 5, 4 };
 
        twoWaySort(arr, arr.Length);
 
        Console.WriteLine(String.Join(" ", arr));
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript program sort array
// in even and odd manner.
// The odd numbers are to be
// sorted in descending
// order and the even numbers in
// ascending order
     
    // To do two way sort.
    // First sort even numbers in
    // ascending order, then odd
    // numbers in descending
    // order.
    function twoWaySort(arr,n)
    {
        // Current indexes from
        // left and right
        let l = 0, r = n - 1;
   
        // Count of odd numbers
        let k = 0;
   
        while (l < r)
        {
           
            // Find first even number
            // from left side.
            while (arr[l] % 2 != 0)
            {
                l++;
                k++;
            }
   
            // Find first odd number
            // from right side.
            while (arr[r] % 2 == 0 && l < r)
                r--;
   
            // Swap even number present
            // on left and odd
            // number right.
            if (l < r)
            {
               
                // swap arr[l] arr[r]
                let temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
           
        let odd=new Array(k);
        for(let i=0;i<k;i++)
        {
            odd[i]=arr[i];
        }
        let even=new Array(n-k);
        for(let i=0;i<n-k;i++)
        {
            even[i]=arr[k+i];
        }
        // Sort odd number in descending order
        odd.sort(function(a,b){return b-a;});
        // Sort even number in ascending order
        even.sort(function(a,b){return a-b;});
         
        return odd.concat(even);
        
    }
    // Driver Method
    let arr=[1, 3, 2, 7, 5, 4 ];
    let ans=twoWaySort(arr, arr.length);
    for(let i=0;i<ans.length;i++)
    {
        document.write(ans[i]+" ");
    }
     
     
    // This code is contributed by rag2127
 
</script>

7 5 3 1 2 4 

Complejidad temporal: O(n log n) 
Espacio auxiliar: O(1)

Método 2 (usando la multiplicación negativa):  

1. Haz que todos los números impares sean negativos.
2. Ordenar todos los números.
3. Revierta los cambios realizados en el paso 1 para recuperar los elementos originales.

Implementación:

// C++ program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
#include <bits/stdc++.h>
using namespace std;
 
// To do two way sort. First sort even numbers in
// ascending order, then odd numbers in descending
// order.
void twoWaySort(int arr[], int n)
{
    // Make all odd numbers negative
    for (int i = 0; i < n; i++)
        if (arr[i] & 1) // Check for odd
            arr[i] *= -1;
 
    // Sort all numbers
    sort(arr, arr + n);
 
    // Retaining original array
    for (int i = 0; i < n; i++)
        if (arr[i] & 1)
            arr[i] *= -1;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 7, 5, 4 };
    int n = sizeof(arr) / sizeof(int);
    twoWaySort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

// Java program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
 
import java.util.Arrays;
 
public class GFG
{
    // To do two way sort. First sort even numbers in
    // ascending order, then odd numbers in descending
    // order.
    static void twoWaySort(int arr[], int n)
    {
        // Make all odd numbers negative
        for (int i = 0; i < n; i++)
            if ((arr[i] & 1) != 0) // Check for odd
                arr[i] *= -1;
 
        // Sort all numbers
        Arrays.sort(arr);
 
        // Retaining original array
        for (int i = 0; i < n; i++)
            if ((arr[i] & 1) != 0)
                arr[i] *= -1;
    }
 
    // Driver Method
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 2, 7, 5, 4 };
 
        twoWaySort(arr, arr.length);
 
        System.out.println(Arrays.toString(arr));
    }
}

# Python 3 program to sort array in
# even and odd manner. The odd
# numkbers are to be sorted in
# descending order and the even
# numbers in ascending order
 
# To do two way sort. First sort
# even numbers in ascending order,
# then odd numbers in descending order.
def twoWaySort(arr, n):
 
    # Make all odd numbers negative
    for i in range(0, n):
         
        # Check for odd
        if (arr[i] & 1):
            arr[i] *= -1
 
    # Sort all numbers
    arr.sort()
 
    # Retaining original array
    for i in range(0, n):
        if (arr[i] & 1):
            arr[i] *= -1
 
# Driver code
arr = [1, 3, 2, 7, 5, 4]
n = len(arr)
twoWaySort(arr, n);
for i in range(0, n):
    print(arr[i], end = " ")
     
# This code is contributed by Smitha Dinesh Semwal

// Java program sort array in even and
// odd manner. The odd numbers are to
// be sorted in descending order and
// the even numbers in ascending order
using System;
 
public class GFG
{
 
    // To do two way sort. First sort
    // even numbers in ascending order,
    // then odd numbers in descending
    // order.
    static void twoWaySort(int[] arr, int n)
    {
 
        // Make all odd numbers negative
        for (int i = 0; i < n; i++)
 
            // Check for odd
            if ((arr[i] & 1) != 0)
                arr[i] *= -1;
 
        // Sort all numbers
        Array.Sort(arr);
 
        // Retaining original array
        for (int i = 0; i < n; i++)
            if ((arr[i] & 1) != 0)
                arr[i] *= -1;
    }
 
    // Driver Method
    public static void Main()
    {
        int[] arr = { 1, 3, 2, 7, 5, 4 };
 
        twoWaySort(arr, arr.Length);
 
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by Smitha

<?php
// PHP program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
 
// To do two way sort. First sort even numbers in
// ascending order, then odd numbers in descending
// order.
function twoWaySort(&$arr, $n)
{
    // Make all odd numbers negative
    for ($i = 0 ; $i < $n; $i++)
        if ($arr[$i] & 1) // Check for odd
            $arr[$i] *= -1;
 
    // Sort all numbers
    sort($arr);
 
    // Retaining original array
    for ($i = 0 ; $i < $n; $i++)
        if ($arr[$i] & 1)
            $arr[$i] *= -1;
}
 
// Driver code
$arr = array(1, 3, 2, 7, 5, 4);
$n = sizeof($arr);
twoWaySort($arr, $n);
for ($i = 0; $i < $n; $i++)
    echo $arr[$i] . " ";
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript program sort array in even and odd manner.
// The odd numbers are to be sorted in descending
// order and the even numbers in ascending order
 
// To do two way sort. First sort even numbers in
// ascending order, then odd numbers in descending
// order.
function twoWaySort(arr, n)
{
    // Make all odd numbers negative
    for (let i = 0; i < n; i++)
        if (arr[i] & 1) // Check for odd
            arr[i] *= -1;
 
    // Sort all numbers
    arr.sort((a,b) => a-b);
 
    // Retaining original array
    for (let i = 0; i < n; i++)
        if (arr[i] & 1)
            arr[i] *= -1;
}
 
// Driver code
 
    let arr = [ 1, 3, 2, 7, 5, 4 ];
    let n = arr.length;
    twoWaySort(arr, n);
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
     
//This code is contributed by Mayank Tyagi
</script>

7 5 3 1 2 4 

Complejidad temporal: O(n log n) 
Espacio auxiliar: O(1)

Es posible que este método no funcione cuando la array de entrada contiene números negativos. Sin embargo, hay una manera de manejar esto. Contamos los enteros impares positivos en la array de entrada y luego ordenamos nuevamente. Los lectores pueden consultar esto para su implementación.

Método 3 (usando el comparador): 
este problema se puede resolver fácilmente usando la función de clasificación incorporada con un método de comparación personalizado. Al comparar dos elementos cualesquiera habrá tres casos: 

1. Cuando ambos elementos son pares: en este caso, el elemento más pequeño debe aparecer a la izquierda del elemento más grande en la array ordenada.
2. Cuando ambos elementos son impares: El elemento más grande debe aparecer a la izquierda del elemento más pequeño.
3. Uno es impar y el otro es par: El elemento que es impar debe aparecer a la izquierda del elemento par.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to print
// the contents of the array
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// To do two way sort. Make comparator function
// for the inbuilt sort function of c++ such that
// odd numbers are placed before even in descending
// and ascending order respectively
bool compare(int a, int b)
{
     
    // If both numbers are even,
    // smaller number should
    // be placed at lower index
    if (a % 2 == 0 && b % 2 == 0)
        return a < b;
 
    // If both numbers are odd larger number
    // should be placed at lower index
    if (a % 2 != 0 && b % 2 != 0)
        return b < a;
 
    // If a is odd and b is even,
    // a should be placed before b
    if (a % 2 != 0)
        return true;
 
    // If b is odd and a is even,
    // b should be placed before a
    return false;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 7, 5, 4 };
    int n = sizeof(arr) / sizeof(int);
 
    // Sort the array
    sort(arr, arr + n, compare);
 
    // Print the sorted array
    printArr(arr, n);
 
    return 0;
}
 
// This code is contributed by Nikhil Yadav

// Java implementation of the approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
class GFG
{
 
    // Utility function to print
    // the contents of the array
    static void printArr(ArrayList<Integer> arr, int n) {
        for (int i = 0; i < n; i++)
            System.out.print(arr.get(i) + " ");
    }
 
    // Driver code
    public static void main(String args[]) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        arr.add(3);
        arr.add(2);
        arr.add(7);
        arr.add(5);
        arr.add(4);
        int n = arr.size();
 
 
        // Sort the array
        Collections.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
 
                // If both numbers are even,
                // smaller number should
                // be placed at lower index
                if (a % 2 == 0 && b % 2 == 0)
                    return (a - b);
 
                // If both numbers are odd larger number
                // should be placed at lower index
                if (a % 2 != 0 && b % 2 != 0)
                    return (b - a);
 
                // If a is odd and b is even,
                // a should be placed before b
                if (a % 2 != 0)
                    return -1;
 
                // If b is odd and a is even,
                // b should be placed before a
                return 0;
            }
        });
         
        // Print the sorted array
        printArr(arr, n);
    }
}
 
// This code is contributed by Saurabh Jaiswal

# Python3 implementation of the approach
 
# Utility function to print
# the contents of the array
from functools import cmp_to_key
 
def printArr(arr, n):
             
    for i in range(n):
        print(arr[i], end = " ")
 
        # To do two way sort. Make comparator function
        # for the inbuilt sort function of c++ such that
        # odd numbers are placed before even in descending
        # and ascending order respectively
def compare(a, b):
 
    # If both numbers are even,
    # smaller number should
    # be placed at lower index
    if (a % 2 == 0 and b % 2 == 0 and a < b):
        return -1
 
    # If both numbers are odd larger number
    # should be placed at lower index
    if (a % 2 != 0 and b % 2 != 0 and b > a):
        return 1
 
    # If a is odd and b is even,
    # a should be placed before b
    if (a % 2 != 0):
        return -1
 
    # If b is odd and a is even,
    # b should be placed before a
    return 1
 
# Driver code
arr = [1, 3, 2, 7, 5, 4]
n = len(arr)
 
# Sort the array
arr.sort(key = cmp_to_key(compare))
 
# Print the sorted array
printArr(arr, n)
         
# This code is contributed by shinjanpatra

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Utility function to print
  // the contents of the array
  static void printArr(List<int> arr, int n) {
    for (int i = 0; i < n; i++)
      Console.Write(arr[i] + " ");
  }
  private static int Compare(int a, int b)
  {
 
    // If both numbers are even,
    // smaller number should
    // be placed at lower index
    if (a % 2 == 0 && b % 2 == 0 && a<b)
      return -1;
 
    // If both numbers are odd larger number
    // should be placed at lower index
    if (a % 2 != 0 && b % 2 != 0 && b>a)
      return 1;
 
    // If a is odd and b is even,
    // a should be placed before b
    if (a % 2 != 0)
      return -1;
 
    // If b is odd and a is even,
    // b should be placed before a
    return 1;
  }
 
  // Driver code
  public static void Main(String []args) {
    List<int> arr = new List<int>();
    arr.Add(1);
    arr.Add(3);
    arr.Add(2);
    arr.Add(7);
    arr.Add(5);
    arr.Add(4);
    int n = arr.Count;
 
    // Sort the array
    arr.Sort(Compare);
 
    // Print the sorted array
    printArr(arr, n);
  }
}
 
 
// This code is contributed by 29AjayKumar

<script>
        // JavaScript implementation of the approach
 
        // Utility function to print
        // the contents of the array
        function printArr(arr, n)
        {
            for (let i = 0; i < n; i++)
                document.write(arr[i] + " ");
        }
 
        // To do two way sort. Make comparator function
        // for the inbuilt sort function of c++ such that
        // odd numbers are placed before even in descending
        // and ascending order respectively
        function compare(a, b) {
 
            // If both numbers are even,
            // smaller number should
            // be placed at lower index
            if (a % 2 == 0 && b % 2 == 0 && a < b)
                return -1;
 
            // If both numbers are odd larger number
            // should be placed at lower index
            if (a % 2 != 0 && b % 2 != 0 && b > a)
                return 1;
 
            // If a is odd and b is even,
            // a should be placed before b
            if (a % 2 != 0)
                return -1;
 
            // If b is odd and a is even,
            // b should be placed before a
            return 1;
        }
 
        // Driver code
        var arr = [1, 3, 2, 7, 5, 4];
        var n = arr.length;
 
        // Sort the array
        arr.sort(compare);
 
        // Print the sorted array
        printArr(arr, n);
         
// This code is contributed by Potta Lokesh
    </script>

7 5 3 1 2 4 

Complejidad de tiempo: O(n*logn) [ la función de clasificación tiene una complejidad de tiempo promedio n*logn]
Espacio auxiliar: O(1)

Gracias a Amandeep Singh por sugerir esta solución.

Este artículo es una contribución de DANISH_RAZA . 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.