Ordenar una array donde un subarreglo de una array ordenada está en orden inverso

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *