Рубрики

Найти минимальный размер несортированного подмассива, сортировка которого позволяет отсортировать весь массив

Для несортированного массива arr [0..n-1] размера n найдите подмассив минимальной длины arr [s..e], чтобы при сортировке этого подмассива весь массив был отсортирован.

Примеры:

1) Если входной массив [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], ваша программа должна быть в состоянии обнаружить, что подмассив находится между индексами 3 и 8.

2) Если входной массив [0, 1, 15, 25, 6, 7, 30, 40, 50], ваша программа должна быть в состоянии обнаружить, что подрешетка находится между индексами 2 и 5.

Решение:
1) Найти кандидата в несортированном подмассиве
а) Сканирование слева направо и найти первый элемент, который больше, чем следующий элемент. Пусть s будет индексом такого элемента. В приведенном выше примере 1 s равен 3 (индекс 30).
б) Сканирование справа налево и найти первый элемент (сначала в порядке справа налево), который меньше, чем следующий элемент (следующий в порядке справа налево). Пусть e будет индексом такого элемента. В приведенном выше примере 1 е равно 7 (индекс 31).

2) Проверьте, сортирует ли выбранный несортированный подмассив весь массив или нет. Если нет, то включите больше элементов в подмассив.
а) Найти минимальное и максимальное значения в arr [s..e] . Пусть минимальные и максимальные значения будут минимальными и максимальными . min и max для [30, 25, 40, 32, 31] составляют 25 и 40 соответственно.
б) Найдите первый элемент (если он есть) в arr [0..s-1], который больше min , замените s на индекс этого элемента. В вышеприведенном примере 1 такого элемента нет.
c) Найдите последний элемент (если он есть) в arr [e + 1..n-1], который меньше max, замените e на индекс этого элемента. В приведенном выше примере 1, е изменено на 8 (индекс 35)

3) Распечатать с и е .

Реализация:

C ++

// C ++ программа для поиска несортированной минимальной длины подмассива,
// сортировка, которая делает весь массив отсортированным
#include<bits/stdc++.h>

using namespace std;

  

void printUnsorted(int arr[], int n)

{

int s = 0, e = n-1, i, max, min; 

  
// шаг 1 (а) указанного выше алгоритма

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;

}

  
// шаг 1 (b) указанного выше алгоритма

for(e = n - 1; e > 0; e--)

{

    if(arr[e] < arr[e-1])

    break;

}

  
// шаг 2 (а) указанного выше алгоритма
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];

}

  
// шаг 2 (b) указанного выше алгоритма

for( i = 0; i < s; i++)

{

    if(arr[i] > min)

    

    s = i;

    break;

    }     

  
// шаг 2 (с) вышеуказанного алгоритма

for( i = n -1; i >= e+1; i--)

{

    if(arr[i] < max)

    {

    e = i;

    break;

    

      
// шаг 3 вышеприведенного алгоритма

cout << "The unsorted subarray which" 

     << " makes the given array" << endl

     << "sorted lies between the indees " 

     << 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;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа для поиска несортированной минимальной длины подмассива,
// сортировка, которая делает весь массив отсортированным
#include<stdio.h>

   

void printUnsorted(int arr[], int n)

{

  int s = 0, e = n-1, i, max, min;   

   

  // шаг 1 (а) указанного выше алгоритма

  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;

  }

   

  // шаг 1 (b) указанного выше алгоритма

  for(e = n - 1; e > 0; e--)

  {

    if(arr[e] < arr[e-1])

      break;

  }

   

  // шаг 2 (а) указанного выше алгоритма

  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];

  }

   

  // шаг 2 (b) указанного выше алгоритма

  for( i = 0; i < s; i++)

  {

    if(arr[i] > min)

    {  

      s = i;

      break;

    }      

  

   

  // шаг 2 (с) вышеуказанного алгоритма

  for( i = n -1; i >= e+1; i--)

  {

    if(arr[i] < max)

    {

      e = i;

      break;

    

  }  

       

  // шаг 3 вышеприведенного алгоритма

  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-программа для поиска Unsorted Subarray минимальной длины,
// сортировка, которая делает весь массив отсортированным

class Main

{

    static void printUnsorted(int arr[], int n)

    {

      int s = 0, e = n-1, i, max, min;   

        

      // шаг 1 (а) указанного выше алгоритма

      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;

      }

        

      // шаг 1 (b) указанного выше алгоритма

      for(e = n - 1; e > 0; e--)

      {

        if(arr[e] < arr[e-1])

          break;

      }

        

      // шаг 2 (а) указанного выше алгоритма

      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];

      }

        

      // шаг 2 (b) указанного выше алгоритма

      for( i = 0; i < s; i++)

      {

        if(arr[i] > min)

        {  

          s = i;

          break;

        }      

      

        

      // шаг 2 (с) вышеуказанного алгоритма

      for( i = n -1; i >= e+1; i--)

      {

        if(arr[i] < max)

        {

          e = i;

          break;

        

      }  

            

      // шаг 3 вышеприведенного алгоритма

      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 программа для поиска несортированной минимальной длины подмассива,
# сортировка, которая делает весь массив отсортированным

def printUnsorted(arr, n):

    e = n-1

    # шаг 1 (а) вышеуказанного алгоритма

    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()

  

    # шаг 1 (б) вышеуказанного алгоритма

    e= n-1

    while e > 0:

        if arr[e] < arr[e-1]:

            break

        e -= 1

  

    # шаг 2 (а) вышеуказанного алгоритма

    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]

              

    # шаг 2 (б) вышеуказанного алгоритма

    for i in range(s):

        if arr[i] > min:

            s = i

            break

  

    # шаг 2 (с) вышеуказанного алгоритма

    i = n-1

    while i >= e+1:

        if arr[i] < max:

            e = i

            break

        i -= 1

      

    # шаг 3 вышеприведенного алгоритма

    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)

  
# Этот код предоставлен Shreyanshi Arun

C #

// C # программа для поиска несортированной минимальной длины подмассива,
// сортировка, которая делает весь массив отсортированным

  

using System;

  

class GFG

{

    static void printUnsorted(int []arr, int n)

    {

    int s = 0, e = n-1, i, max, min; 

          

    // шаг 1 (а) указанного выше алгоритма

    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;

    }

          

    // шаг 1 (b) указанного выше алгоритма

    for(e = n - 1; e > 0; e--)

    {

        if(arr[e] < arr[e-1])

        break;

    }

          

    // шаг 2 (а) указанного выше алгоритма

    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];

    }

          

    // шаг 2 (b) указанного выше алгоритма

    for( i = 0; i < s; i++)

    {

        if(arr[i] > min)

        

            s = i;

            break;

        }     

    

          

    // шаг 2 (с) вышеуказанного алгоритма

    for( i = n -1; i >= e+1; i--)

    {

        if(arr[i] < max)

        {

            e = i;

            break;

        

    

              

    // шаг 3 вышеприведенного алгоритма

    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);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php 
// PHP-программа для поиска несортированной минимальной длины подмассива,
// сортировка, которая делает весь массив отсортированным

function printUnsorted(&$arr, $n)

{

    $s = 0;

    $e = $n - 1;

      

    // шаг 1 (а) указанного выше алгоритма

    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;

    }

      

    // шаг 1 (b) указанного выше алгоритма

    for($e = $n - 1; $e > 0; $e--)

    {

        if($arr[$e] < $arr[$e - 1])

        break;

    }

      

    // шаг 2 (а) указанного выше алгоритма

    $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];

    }

      

    // шаг 2 (b) указанного выше алгоритма

    for( $i = 0; $i < $s; $i++)

    {

        if($arr[$i] > $min)

        

            $s = $i;

            break;

        }     

    

      

    // шаг 2 (с) вышеуказанного алгоритма

    for( $i = $n - 1; $i >= $e + 1; $i--)

    {

        if($arr[$i] < $max)

        {

            $e = $i;

            break;

        

    

          

    // шаг 3 вышеприведенного алгоритма

    echo " The unsorted subarray which makes "

                     "the given array " . "\n"

            " sorted lies between the indees "

                              $s . " and " . $e;

    return;

}

  
// Код драйвера

$arr = array(10, 12, 20, 30, 25, 40, 

             32, 31, 35, 50, 60);

$arr_size = sizeof($arr);

printUnsorted($arr, $arr_size);

  
// Этот код добавлен
// ChitraNayal
?>

Выход :

 The unsorted subarray which makes the given array 
sorted lies between the indees 3 and 8

Сложность времени: O (n)

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

Рекомендуемые посты:

Найти минимальный размер несортированного подмассива, сортировка которого позволяет отсортировать весь массив

0.00 (0%) 0 votes