Sort first half in ascending and second half in descending order | Set 2

0 0 5 minutes read

Given an array of integers, sort the first half of the array in ascending order and the second half in descending order.

Examples:

Input : arr[] = {10, 20, 30, 40}
Output : arr[] = {10, 20, 40, 30}

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

We have discussed a solution that only prints the required order in Sort first half in ascending and second half in descending order | Set 1

Simple Approach: The idea is simple, we sort the first half in increasing order and the second half in decreasing using the library function. Most of the languages like Java, C++ provide provision to sort a subarray in a specified order. In this post, a different solution is discussed that modifies the original array.

Implementation:

C++

// C++ program to sort first half in increasing
// order and second half in decreasing
#include<bits/stdc++.h>
using namespace std;
 
void mySort(int arr[], int n)
{
    sort(arr, arr+n/2);
    sort(arr+n/2, arr+n, greater<int>());
}
 
int main()
{
    int arr[] = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
    int n = sizeof(arr)/sizeof(arr[0]);
    mySort(arr, n);
    cout << "Modified Array : \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

Java

// Java program to sort first half in increasing
// order and second half in decreasing
import java.util.*;
 
public class SortExample {
    static void mySort(Integer[] arr)
    {
        int n = arr.length;
 
        // Sort subarray from index 1 to 4, i.e.,
        // only sort subarray {7, 6, 45, 21} and
        // keep other elements as it is.
        Arrays.sort(arr, 0, n / 2);
        Arrays.sort(arr, n / 2, n, Collections.reverseOrder());
    }
 
    public static void main(String[] args)
    {
        // Our arr contains 8 elements
        Integer[] arr = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
        mySort(arr);
        System.out.printf("Modified arr[] : %s",
                          Arrays.toString(arr));
    }
}

Python 3

# Python3 program to sort first half in increasing
# order and second half in decreasing
 
# required sorting function
def mySort( arr, n):
     
    arr1 = arr[:n//2]
    arr2 = arr[n//2:]
    arr1.sort()
    arr2.sort(reverse=True)
    return arr1+arr2
     
     
 
# driving function
if __name__=='__main__':
    arr= [5, 4, 6, 2, 1, 3, 8, 9, 7 ]
    n = len(arr)
    arr=mySort(arr, n)
    print( "Modified Array : ")
    print(arr)
 
# this code is contributed by ash264

C#

// C# program to sort first half in increasing
// order and second half in decreasing
using System;
 
public class SortExample
{
    static void mySort(int[] arr)
    {
        int n = arr.Length;
 
        // Sort subarray from index 1 to 4, i.e.,
        // only sort subarray {7, 6, 45, 21} and
        // keep other elements as it is.
        Array.Sort(arr, 0, n / 2);
        Array.Sort(arr, n / 2, (n/2)+1);
        Array.Reverse(arr, n / 2, (n/2)+1);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Our arr contains 8 elements
        int[] arr = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
        mySort(arr);
        Console.Write("Modified arr[] : {0}",
                        String.Join(" ",arr));
    }
}
 
/* This code contributed by PrinciRaj1992 */

PHP

<?php
// PHP program to sort first half in increasing
// order and second half in decreasing
 
function mySort(&$arr, $n)
{
    $array1 = array_slice($arr, 0,
                    floor($n / 2));
    $array2 = array_slice($arr, $n / 2);
    sort($array1);
    rsort($array2);
    $arr = array_merge($array1, $array2);
}
 
// Driver Code
$arr = array(5, 4, 6, 2, 1, 3, 8, 9, 7);
$n = sizeof($arr);
mySort($arr, $n);
 
echo "Modified array :\n";
for($i = 0; $i < $n; $i++)
    echo $arr[$i] . " ";
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript program to sort
// first half in increasing
// order and second half in decreasing
     
    function mySort(arr)
    {
        let n = arr.length;
   
        // Sort subarray from index 1 to 4, i.e.,
        // only sort subarray {7, 6, 45, 21} and
        // keep other elements as it is.
         
        let arr1=arr.slice(0,Math.floor(n/2)).
        sort(function(a,b){return a-b;});
        let arr2=arr.slice(Math.floor(n/2),
        Math.floor(n/2)+n).sort(function(a,b)
        {return b-a;})
        return arr1.concat(arr2)
    }
     
    // Our arr contains 8 elements
    let arr=[5, 4, 6, 2, 1, 3, 8, 9, 7];
    arr=mySort(arr);
    document.write("Modified arr : <br>"+arr.join(" "));
     
 
 
// This code is contributed by rag2127
 
</script>

Output

Modified Array : 
2 4 5 6 9 8 7 3 1

Complexity Analysis:

Time Complexity: O(N*logN)
Auxiliary Space: O(1)

Alternate Solution:

Sort the whole array in ascending order.
Reverse the second half after sorting.

Implementation:

C++

// C++ program to sort first half in increasing
// order and second half in decreasing
#include<bits/stdc++.h>
using namespace std;
 
void mySort(int arr[], int n)
{
    // Sort the first half
    sort(arr, arr+n/2);
    sort(arr+n/2, arr+n);
 
    reverse(arr+n/2, arr+n);
}
 
int main()
{
    int arr[] = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
    int n = sizeof(arr)/sizeof(arr[0]);
    mySort(arr, n);
    cout << "Modified Array : \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

Java

// Java program to sort first half in increasing
// order and second half in decreasing
import java.util.*;
 
public class SortExample {
    static void mySort(Integer[] arr)
    {
        int n = arr.length;
         
        // Sort the whole array
        Arrays.sort(arr, 0, n/2);
        Arrays.sort(arr, n/2, n);
 
        // Reverse the second half
        int low = n/2, high = n-1;
        while (low < high)
        {
            Integer temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++; high--;
        } 
    }
 
    public static void main(String[] args)
    {
        // Our arr contains 8 elements
        Integer[] arr = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
        mySort(arr);
        System.out.printf("Modified arr[] : %s",
                          Arrays.toString(arr));
    }
}

Python3

# Python3 program to sort first half in increasing
# order and second half in decreasing
def mySort(arr):
    n = len(arr);
 
    # Sort the whole array
    arr1 = arr[:n // 2]
    arr2 = arr[n // 2:]
    arr1.sort()
    arr2.sort()
    arr = arr1 + arr2
 
    # Reverse the second half
    low = n // 2;
    high = n - 1;
    while (low < high):
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
        low += 1;
        high -= 1;
    return arr;
 
# Driver code
if __name__ == '__main__':
     
    # Our arr contains 8 elements
    arr = [5, 4, 6, 2, 1, 3, 8, 9, 7];
    arr = mySort(arr);
    print("Modified Array : ")
    print(arr)
 
# This code is contributed by 29AjayKumar

C#

// C# program to sort first half in increasing
// order and second half in decreasing
using System;
 
public class SortExample
{
    static void mySort(int[] arr)
    {
        int n = arr.Length;
         
        // Sort the whole array
        Array.Sort(arr, 0, n/2);
        Array.Sort(arr, n/2, n/2+1);
 
        // Reverse the second half
        int low = n/2, high = n-1;
        while (low < high)
        {
            int temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++; high--;
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Our arr contains 8 elements
        int[] arr = { 5, 4, 6, 2, 1, 3, 8, 9, 7 };
        mySort(arr);
        Console.WriteLine("Modified arr[] : {0}",
                        String.Join(", ",arr));
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// Javascript program to sort first half in increasing
// order and second half in decreasing
     
    function mySort(arr)
    {
        let n = arr.length;
           
         // Sort the whole array  
        let arr1=arr.slice(0,Math.floor(n/2)).sort(function(a,b){return a-b;});
        let arr2=arr.slice(Math.floor(n/2),n).sort(function(a,b){return a-b;});
        arr=arr1.concat(arr2);
   
        // Reverse the second half
        let low = Math.floor(n/2), high = n-1;
        while (low < high)
        {
            let temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++; high--;
        }
        return arr;
    }
     
    let arr=[5, 4, 6, 2, 1, 3, 8, 9, 7 ];
    arr=mySort(arr);
    document.write("Modified arr : "+arr.join(" "));
     
 
// This code is contributed by avanitrachhadiya2155
</script>