In: Computer Science
Write a method that takes an array of integers as input. The method should find and display two indices m and n such that if you sort the elements from index m to index n the entire array would be sorted. The method should minimize m − n, that is it should find the smallest subsection for the array that needs to be sorted. For example,
int[] a = {2, 4, 6, 7, 9, 8, 12, 15, 5, 13, 18, 20}
get_unsorted_section(a); // prints 2 and 9
Please use Java. Thanks!
class Main
{
static void get_unsorted_section(int arr[], int n)
{
int s = 0, e = n-1, i, max, min;
for (s = 0; s < n-1; s++)
{
if (arr[s] > arr[s+1])
break;
}
if (s == n-1)
{
return;
}
for(e = n - 1; e > 0; e--)
{
if(arr[e] < arr[e-1])
break;
}
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];
}
for( i = 0; i < s; i++)
{
if(arr[i] > min)
{
s = i;
break;
}
}
for( i = n -1; i >= e+1; i--)
{
if(arr[i] < max)
{
e = i;
break;
}
}
System.out.println(s+" "+e);
return;
}
public static void main(String args[])
{
int arr[] = {2, 4, 6, 7, 9, 8, 12, 15, 5, 13, 18, 20};
int arr_size = arr.length;
get_unsorted_section(arr, arr_size);
}
}
Here is the desire code. Please check it out. I hope it
helps.
Thank you