Encuentre el subarreglo sin ordenar de longitud mínima, ordenando lo que hace que el arreglo completo esté ordenado

Posted on by Rudeus Greyrat

Dada una array no ordenada arr[0..n-1] de tamaño n, encuentre la longitud mínima de subarreglo arr[s..e] tal que al ordenar este subarreglo se ordene todo el arreglo. 
Ejemplos: 

  1. Si el arreglo de entrada es [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], su programa debería poder encontrar que el subarreglo se encuentra entre los índices 3 y 8.
  2. Si el arreglo de entrada es [0, 1, 15, 25, 6, 7, 30, 40, 50], su programa debería poder encontrar que el subarreglo se encuentra entre los índices 2 y 5.

Solución: 

C++

// C++ program to find the Minimum length Unsorted Subarray, 
// sorting which makes the complete array sorted
#include<bits/stdc++.h>
using namespace std;
  
void printUnsorted(int arr[], int n)
{
int s = 0, e = n-1, i, max, min; 
  
// step 1(a) of above algo
for (s = 0; s < n-1; s++)
{
    if (arr[s] > arr[s+1])
    break;
}
if (s == n-1)
{
    cout << "The complete array is sorted";
    return;
}
  
// step 1(b) of above algo
for(e = n - 1; e > 0; e--)
{
    if(arr[e] < arr[e-1])
    break;
}
  
// step 2(a) of above algo
max = arr[s]; min = arr[s];
for(i = s + 1; i <= e; i++)
{
    if(arr[i] > max)
    max = arr[i];
    if(arr[i] < min)
    min = arr[i];
}
  
// step 2(b) of above algo
for( i = 0; i < s; i++)
{
    if(arr[i] > min)
    { 
    s = i;
    break;
    }     
} 
  
// step 2(c) of above algo
for( i = n -1; i >= e+1; i--)
{
    if(arr[i] < max)
    {
    e = i;
    break;
    } 
} 
      
// step 3 of above algo
cout << "The unsorted subarray which" 
     << " makes the given array" << endl
     << "sorted lies between the indices " 
     << s << " and " << e;
return;
}
  
int main()
{
    int arr[] = {10, 12, 20, 30, 25,
                 40, 32, 31, 35, 50, 60};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printUnsorted(arr, arr_size);
    getchar();
    return 0;
}
  
// This code is contributed 
// by Akanksha Rai

C

// C program to find the Minimum length Unsorted Subarray, 
// sorting which makes the complete array sorted
#include<stdio.h>
   
void printUnsorted(int arr[], int n)
{
  int s = 0, e = n-1, i, max, min;   
   
  // step 1(a) of above algo
  for (s = 0; s < n-1; s++)
  {
    if (arr[s] > arr[s+1])
      break;
  }
  if (s == n-1)
  {
    printf("The complete array is sorted");
    return;
  }
   
  // step 1(b) of above algo
  for(e = n - 1; e > 0; e--)
  {
    if(arr[e] < arr[e-1])
      break;
  }
   
  // step 2(a) of above algo
  max = arr[s]; min = arr[s];
  for(i = s + 1; i <= e; i++)
  {
    if(arr[i] > max)
      max = arr[i];
    if(arr[i] < min)
      min = arr[i];
  }
   
  // step 2(b) of above algo
  for( i = 0; i < s; i++)
  {
    if(arr[i] > min)
    {  
      s = i;
      break;
    }      
  } 
   
  // step 2(c) of above algo
  for( i = n -1; i >= e+1; i--)
  {
    if(arr[i] < max)
    {
      e = i;
      break;
    } 
  }  
       
  // step 3 of above algo
  printf(" The unsorted subarray which makes the given array "
         " sorted lies between the indees %d and %d", s, e);
  return;
}
   
int main()
{
  int arr[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printUnsorted(arr, arr_size);
  getchar();
  return 0;
}

Java

// Java program to find the Minimum length Unsorted Subarray, 
// sorting which makes the complete array sorted
class Main
{
    static void printUnsorted(int arr[], int n)
    {
      int s = 0, e = n-1, i, max, min;   
        
      // step 1(a) of above algo
      for (s = 0; s < n-1; s++)
      {
        if (arr[s] > arr[s+1])
          break;
      }
      if (s == n-1)
      {
        System.out.println("The complete array is sorted");
        return;
      }
        
      // step 1(b) of above algo
      for(e = n - 1; e > 0; e--)
      {
        if(arr[e] < arr[e-1])
          break;
      }
        
      // step 2(a) of above algo
      max = arr[s]; min = arr[s];
      for(i = s + 1; i <= e; i++)
      {
        if(arr[i] > max)
          max = arr[i];
        if(arr[i] < min)
          min = arr[i];
      }
        
      // step 2(b) of above algo
      for( i = 0; i < s; i++)
      {
        if(arr[i] > min)
        {  
          s = i;
          break;
        }      
      } 
        
      // step 2(c) of above algo
      for( i = n -1; i >= e+1; i--)
      {
        if(arr[i] < max)
        {
          e = i;
          break;
        } 
      }  
            
      // step 3 of above algo
      System.out.println(" The unsorted subarray which"+
                         " makes the given array sorted lies"+
                       "  between the indices "+s+" and "+e);
      return;
    }
        
    public static void main(String args[])
    {
      int arr[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};
      int arr_size = arr.length;
      printUnsorted(arr, arr_size);
    }
}

Python3

# Python3 program to find the Minimum length Unsorted Subarray, 
# sorting which makes the complete array sorted
def printUnsorted(arr, n):
    e = n-1
    # step 1(a) of above algo
    for s in range(0,n-1):
        if arr[s] > arr[s+1]:
            break
          
    if s == n-1:
        print ("The complete array is sorted")
        exit()
  
    # step 1(b) of above algo
    e= n-1
    while e > 0:
        if arr[e] < arr[e-1]:
            break
        e -= 1
  
    # step 2(a) of above algo
    max = arr[s]
    min = arr[s]
    for i in range(s+1,e+1):
        if arr[i] > max:
            max = arr[i]
        if arr[i] < min:
            min = arr[i]
              
    # step 2(b) of above algo
    for i in range(s):
        if arr[i] > min:
            s = i
            break
  
    # step 2(c) of above algo
    i = n-1
    while i >= e+1:
        if arr[i] < max:
            e = i
            break
        i -= 1
      
    # step 3 of above algo
    print ("The unsorted subarray which makes the given array")
    print ("sorted lies between the indexes %d and %d"%( s, e))
  
arr = [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60]
arr_size = len(arr)
printUnsorted(arr, arr_size)
  
# This code is contributed by Shreyanshi Arun

C#

// C# program to find the Minimum length Unsorted Subarray, 
// sorting which makes the complete array sorted
  
using System;
  
class GFG
{
    static void printUnsorted(int []arr, int n)
    {
    int s = 0, e = n-1, i, max, min; 
          
    // step 1(a) of above algo
    for (s = 0; s < n-1; s++)
    {
        if (arr[s] > arr[s+1])
        break;
    }
    if (s == n-1)
    {
        Console.Write("The complete " +
                            "array is sorted");
        return;
    }
          
    // step 1(b) of above algo
    for(e = n - 1; e > 0; e--)
    {
        if(arr[e] < arr[e-1])
        break;
    }
          
    // step 2(a) of above algo
    max = arr[s]; min = arr[s];
      
    for(i = s + 1; i <= e; i++)
    {
        if(arr[i] > max)
            max = arr[i];
          
        if(arr[i] < min)
            min = arr[i];
    }
          
    // step 2(b) of above algo
    for( i = 0; i < s; i++)
    {
        if(arr[i] > min)
        { 
            s = i;
            break;
        }     
    } 
          
    // step 2(c) of above algo
    for( i = n -1; i >= e+1; i--)
    {
        if(arr[i] < max)
        {
            e = i;
            break;
        } 
    } 
              
    // step 3 of above algo
    Console.Write(" The unsorted subarray which"+
            " makes the given array sorted lies \n"+
              " between the indices "+s+" and "+e);
    return;
    }
          
    public static void Main()
    {
        int []arr = {10, 12, 20, 30, 25, 40,
                                32, 31, 35, 50, 60};
        int arr_size = arr.Length;
          
        printUnsorted(arr, arr_size);
    }
}
  
// This code contributed by Sam007

PHP

<?php 
// PHP program to find the Minimum length Unsorted Subarray, 
// sorting which makes the complete array sorted
function printUnsorted(&$arr, $n)
{
    $s = 0;
    $e = $n - 1;
      
    // step 1(a) of above algo
    for ($s = 0; $s < $n - 1; $s++)
    {
        if ($arr[$s] > $arr[$s + 1])
        break;
    }
    if ($s == $n - 1)
    {
        echo "The complete array is sorted";
        return;
    }
      
    // step 1(b) of above algo
    for($e = $n - 1; $e > 0; $e--)
    {
        if($arr[$e] < $arr[$e - 1])
        break;
    }
      
    // step 2(a) of above algo
    $max = $arr[$s]; 
    $min = $arr[$s];
    for($i = $s + 1; $i <= $e; $i++)
    {
        if($arr[$i] > $max)
            $max = $arr[$i];
        if($arr[$i] < $min)
            $min = $arr[$i];
    }
      
    // step 2(b) of above algo
    for( $i = 0; $i < $s; $i++)
    {
        if($arr[$i] > $min)
        { 
            $s = $i;
            break;
        }     
    } 
      
    // step 2(c) of above algo
    for( $i = $n - 1; $i >= $e + 1; $i--)
    {
        if($arr[$i] < $max)
        {
            $e = $i;
            break;
        } 
    } 
          
    // step 3 of above algo
    echo " The unsorted subarray which makes " . 
                     "the given array " . "\n" . 
            " sorted lies between the indees " . 
                              $s . " and " . $e;
    return;
}
  
// Driver code
$arr = array(10, 12, 20, 30, 25, 40, 
             32, 31, 35, 50, 60);
$arr_size = sizeof($arr);
printUnsorted($arr, $arr_size);
  
// This code is contributed 
// by ChitraNayal
?>

Javascript

<script>
  
// Javascript program to find the Minimum length Unsorted Subarray,  
// sorting which makes the complete array sorted 
      
    function printUnsorted(arr,n)
    {
        let s = 0, e = n-1, i, max, min; 
        // step 1(a) of above algo 
        for (s = 0; s < n-1; s++)
        {
            if (arr[s] > arr[s+1]) 
                break; 
        }
        if (s == n-1) 
        {
            document.write("The complete array is sorted"); 
            return; 
        }
        // step 1(b) of above algo 
        for(e = n - 1; e > 0; e--) 
        {
            if(arr[e] < arr[e-1]) 
                break;
        }
        // step 2(a) of above algo
        max = arr[s]; min = arr[s]; 
        for(i = s + 1; i <= e; i++) 
        {
            if(arr[i] > max)
                max = arr[i];
            if(arr[i] < min) 
                min = arr[i];
        }
        // step 2(b) of above algo 
        for( i = 0; i < s; i++) 
        {
            if(arr[i] > min) 
            {
                s = i; 
                break;
            }
        }
        // step 2(c) of above algo 
        for( i = n -1; i >= e+1; i--) 
        {
            if(arr[i] < max) 
            {
                e = i; 
                break; 
            }
        }
        // step 3 of above algo 
        document.write(" The unsorted subarray which"+ 
                         " makes the given array sorted lies"+ 
                       "  between the indees "+s+" and "+e); 
        return;
    }
    let arr=[10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60];
    let arr_size = arr.length; 
    printUnsorted(arr, arr_size); 
      
    // This code is contributed by avanitrachhadiya2155
      
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *