Tutorialspoint.dev

Sort all even numbers in ascending order and then sort all odd numbers in descending order

Given an array of integers (both odd and even), sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.

Examples:

Input  : arr[] = {1, 2, 3, 5, 4, 7, 10}
Output : arr[] = {7, 5, 3, 1, 2, 4, 10}

Input  : arr[] = {0, 4, 5, 3, 7, 2, 1}
Output : arr[] = {7, 5, 3, 1, 0, 2, 4}

Asked in : Microsoft


Method 1 (Using Partition)



  1. Partition the input array such that all odd elements are moved to left and all even elements on right. This step takes O(n).
  2. Once the array is partitioned, sort left and right parts individually. This step takes O(n Log n).

Below is implementation of above idea.

C++

// 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 odd number from left side.
        while (arr[l]%2 != 0)
        {
            l++;
            k++;
        }
  
        // Find first even number from right side.
        while (arr[r]%2 == 0  && l<r)
            r--;
  
        // Swap odd number present on left and even
        // 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

// 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 odd number from left side.
            while (arr[l]%2 != 0)
            {
                l++;
                k++;
            }
       
            // Find first even number from right side.
            while (arr[r]%2 == 0  && l<r)
                r--;
       
            // Swap odd number present on left and even
            // 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

# 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 swaped
        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 swaped     
        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#

// 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 odd number from left side.
            while (arr[l] % 2 != 0)
            {
                l++;
                k++;
            }
      
            // Find first even number from right side.
            while (arr[r] % 2 == 0 && l < r)
                r--;
      
            // Swap odd number present on left and even
            // 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


Output:

7 5 3 1 2 4

Time complexity: O(n log n)
space complexity: O(1)

 
Method 2 (Using negative multiplication) :

  1. Make all odd numbers negative.
  2. Sort all numbers.
  3. Revert the changes made in step 1 to get original elements back.

C++

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

// 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));
    }
}

Python3

# 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

C#

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


Output:

7 5 3 1 2 4

Time complexity: O(n log n)
Space complexity: O(1)

This method may not work when input array contains negative numbers. However, there is a way to handle this. We count the positive odd integers in the input array then sort again. Readers may refer this for implementation.

Thanks to Amandeep Singh for suggesting this solution.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Arrays Sorting Microsoft Microsoft Arrays Sorting
Prev Next
More topics on Sorting Algorithms

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Sorting Algorithms... Sort all even numbers in ascen...
Sorting Algorithms... Recursive Insertion Sort
Sorting Algorithms... C Program for Bubble Sort on L...
Sorting Algorithms... Minimum swaps to make two arra...
Sorting Algorithms... Chocolate Distribution Problem...
Sorting Algorithms... Number of swaps to sort when o...