Dada una array de enteros, ordene la primera mitad de la array en orden ascendente y la segunda mitad en orden descendente.
Ejemplos:
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 }
Hemos discutido una solución que solo imprime el orden requerido en Ordenar la primera mitad en orden ascendente y la segunda mitad en orden descendente | Serie 1
Enfoque simple
La idea es simple, ordenamos la primera mitad en orden creciente y la segunda mitad en orden decreciente usando la función de biblioteca. La mayoría de los lenguajes como Java, C++ brindan la posibilidad de ordenar un subarreglo en un orden específico. En esta publicación, se analiza una solución diferente que modifica la array original.
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>
Producción:
Modified array : 2 4 5 6 9 8 7 3 1
Complejidad de tiempo: O(N*logN)
Espacio Auxiliar: O(1)
Solución alternativa
1) Ordene toda la array en orden ascendente.
2) Invierta la segunda mitad después de clasificar.
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>
Producción:
Modified arr[] : [2, 4, 5, 6, 9, 8, 7, 3, 1]
Complejidad de tiempo: O(N*logN)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por PrateekRaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA