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 decreasingimport 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 functiondef mySort( arr, n): arr1 = arr[:n//2] arr2 = arr[n//2:] arr1.sort() arr2.sort(reverse=True) return arr1+arr2 # driving functionif __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 decreasingusing 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 decreasingfunction 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 decreasingimport 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 decreasingdef 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 codeif __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 decreasingusing 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> |
Output
Modified Array : 2 4 5 6 9 8 7 3 1
Complexity Analysis:
- Time Complexity: O(N*logN)
- Auxiliary Space: O(1)
