Dada una array de N números donde un subarreglo está ordenado en orden descendente y el resto de los números en la array están en orden ascendente. La tarea es ordenar una array donde un subarreglo de una array ordenada está en orden inverso.
Ejemplos:
Entrada: 2 5 65 55 50 70 90
Salida: 2 5 50 55 65 70 90
El subarreglo del segundo índice al cuarto índice está en orden inverso.
Entonces, el subarreglo se invierte y se imprime el arreglo ordenado.Entrada: 1 7 6 5 4 3 2 8
Salida: 1 2 3 4 5 6 7 8
Un enfoque ingenuo será ordenar la array e imprimir la array. La complejidad temporal de este enfoque será O(N log n).
Un enfoque eficiente será encontrar y almacenar el índice inicial y el índice final del subarreglo invertido. Dado que el subarreglo está en orden descendente y el resto de los elementos están en orden ascendente, solo invertir el subarreglo ordenará el arreglo completo. Invierta el subarreglo usando el enfoque de dos punteros .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sort an array where
// a subarray of a sorted array
// is in reversed order
#include <bits/stdc++.h>
using namespace std;
// Function to print the sorted array
// by reversing the subarray
void printSorted(int a[], int n)
{
int front = -1, back = -1;
// find the starting index of the
// reversed subarray
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
front = i - 1;
break;
}
}
// find the ending index of the
// reversed subarray
for (int i = n - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) {
back = i + 1;
break;
}
}
// if no reversed subarray is present
if (front == -1 and back == -1) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return;
}
// swap the reversed subarray
while (front <= back) {
// swaps the front and back element
// using c++ STL
swap(a[front], a[back]);
// move the pointers one step
// ahead and one step back
front++;
back--;
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
// Driver Code
int main()
{
int a[] = { 1, 7, 6, 5, 4, 3, 2, 8 };
int n = sizeof(a) / sizeof(a[0]);
printSorted(a, n);
return 0;
}
Java
// Java program to sort an array where
// a subarray of a sorted array
// is in reversed order
import java.io.*;
class GFG
{
// Function to print the sorted array
// by reversing the subarray
static void printSorted(int a[], int n)
{
int front = -1, back = -1;
// find the starting index of the
// reversed subarray
for (int i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
front = i - 1;
break;
}
}
// find the ending index of the
// reversed subarray
for (int i = n - 2; i >= 0; i--)
{
if (a[i] > a[i + 1])
{
back = i + 1;
break;
}
}
// if no reversed subarray is present
if (front == -1 && back == -1)
{
for (int i = 0; i < n; i++)
System.out.println(a[i] + " ");
return;
}
// swap the reversed subarray
while (front <= back)
{
// swaps the front and back element
// using c++ STL
int temp = a[front];
a[front] = a[back];
a[back] = temp;
// move the pointers one step
// ahead and one step back
front++;
back--;
}
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
// Driver Code
public static void main (String[] args)
{
int a[] = { 1, 7, 6, 5, 4, 3, 2, 8 };
int n = a.length;
printSorted(a, n);;
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to sort an array where # a subarray of a sorted array is in # reversed order # Function to print the sorted array # by reversing the subarray def printSorted(a, n): front = -1 back = -1 # find the starting index of the # reversed subarray for i in range(1, n, 1): if (a[i] < a[i - 1]): front = i - 1 break # find the ending index of the # reversed subarray i = n - 2 while(i >= 0): if (a[i] > a[i + 1]): back = i + 1 break i -= 1 # if no reversed subarray is present if (front == -1 and back == -1): for i in range(0, n, 1): print(a[i], end = " ") return # swap the reversed subarray while (front <= back): # swaps the front and back element # using c++ STL temp = a[front] a[front] = a[back] a[back] = temp # move the pointers one step # ahead and one step back front += 1 back -= 1 for i in range(0, n, 1): print(a[i], end = " ") # Driver Code if __name__ == '__main__': a = [1, 7, 6, 5, 4, 3, 2, 8] n = len(a) printSorted(a, n) # This code is contributed by # Sahil_Shelangia
C#
// C# program to sort an array where
// a subarray of a sorted array
// is in reversed order
using System;
class GFG
{
// Function to print the sorted array
// by reversing the subarray
static void printSorted(int []a, int n)
{
int front = -1, back = -1;
// find the starting index of the
// reversed subarray
for (int i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
front = i - 1;
break;
}
}
// find the ending index of the
// reversed subarray
for (int i = n - 2; i >= 0; i--)
{
if (a[i] > a[i + 1])
{
back = i + 1;
break;
}
}
// if no reversed subarray is present
if (front == -1 && back == -1)
{
for (int i = 0; i < n; i++)
{
Console.Write(a[i] + " ");
}
return;
}
// swap the reversed subarray
while (front <= back)
{
// swaps the front and back element
// using c++ STL
swap(a, front, back);
// move the pointers one step
// ahead and one step back
front++;
back--;
}
for (int i = 0; i < n; i++)
{
Console.Write(a[i] + " ");
}
}
static void swap(int[] a, int front,
int back)
{
int c = a[front];
a[front] = a[back];
a[back] = c;
}
// Driver Code
public static void Main()
{
int []a = {1, 7, 6, 5, 4, 3, 2, 8};
int n = a.Length;
printSorted(a, n);
}
}
// This code contributed by 29AjayKumar
PHP
<?php
// PHP program to sort an array where
// a subarray of a sorted array
// is in reversed order
// Function to print the sorted array
// by reversing the subarray
function printSorted($a, $n)
{
$front = -1; $back = -1;
// find the starting index of the
// reversed subarray
for ($i = 1; $i < $n; $i++)
{
if ($a[$i] < $a[$i - 1])
{
$front = $i - 1;
break;
}
}
// find the ending index of the
// reversed subarray
for ($i = $n - 2; $i >= 0; $i--)
{
if ($a[$i] > $a[$i + 1])
{
$back = $i + 1;
break;
}
}
// if no reversed subarray is present
if ($front == -1 && $back == -1)
{
for ($i = 0; $i < $n; $i++)
echo $a[$i] . " ";
return;
}
// swap the reversed subarray
while ($front <= $back)
{
// swaps the front and back element
// using c++ STL
$temp = $a[$front];
$a[$front] = $a[$back];
$a[$back] = $temp;
// move the pointers one step
// ahead and one step back
$front++;
$back--;
}
for ($i = 0; $i < $n; $i++)
echo $a[$i] . " ";
}
// Driver Code
$a = array(1, 7, 6, 5, 4, 3, 2, 8);
$n = sizeof($a);
printSorted($a, $n);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// JavaScript program to sort an array where
// a subarray of a sorted array
// is in reversed order
// Function to print the sorted array
// by reversing the subarray
function printSorted(a , n) {
var front = -1, back = -1;
// find the starting index of the
// reversed subarray
for (i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
front = i - 1;
break;
}
}
// find the ending index of the
// reversed subarray
for (i = n - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) {
back = i + 1;
break;
}
}
// if no reversed subarray is present
if (front == -1 && back == -1) {
for (i = 0; i < n; i++)
document.write(a[i] + " ");
return;
}
// swap the reversed subarray
while (front <= back) {
// swaps the front and back element
// using c++ STL
var temp = a[front];
a[front] = a[back];
a[back] = temp;
// move the pointers one step
// ahead and one step back
front++;
back--;
}
for (i = 0; i < n; i++)
document.write(a[i] + " ");
}
// Driver Code
var a = [ 1, 7, 6, 5, 4, 3, 2, 8 ];
var n = a.length;
printSorted(a, n);
// This code is contributed by todaysgaurav
</script>
Producción:
1 2 3 4 5 6 7 8
Complejidad de tiempo: O(n)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por AdityaVerma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA