#include<iostream>
#include<conio.h>
using namespace std;
void printUnsorted(int arr[], int n);
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;
}
void printUnsorted(int arr[], int n)
{
int s = 0, e = n - 1, i, max, min;
//scan from left to right and find the first element which is
//greater then its next element
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;
}
//scan from right to left and find the index of first elemnt which is smaller then next element
for (e = n - 1; e > 0; --e)
if (arr[e] < arr[e - 1]) break;
//find the minimum and smallest element between arr[s..e] subarray
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];
}
//find the first element in arr[0..s - 1] which is greater than min
for (i = 0; i < s; i++)
{
if (arr[i] > min)
{
s = i;
break;
}
}
//find the first element in arr[e+1 .. n-1] which is greater than min
for (i = n - 1; i >= e + 1; --i)
{
if (arr[i] < max)
{
e = i;
break;
}
}
printf(" The unsorted subarray which makes the given array "
" sorted lies between the indees %d and %d", s, e);
return;
}
#include<conio.h>
using namespace std;
void printUnsorted(int arr[], int n);
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;
}
void printUnsorted(int arr[], int n)
{
int s = 0, e = n - 1, i, max, min;
//scan from left to right and find the first element which is
//greater then its next element
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;
}
//scan from right to left and find the index of first elemnt which is smaller then next element
for (e = n - 1; e > 0; --e)
if (arr[e] < arr[e - 1]) break;
//find the minimum and smallest element between arr[s..e] subarray
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];
}
//find the first element in arr[0..s - 1] which is greater than min
for (i = 0; i < s; i++)
{
if (arr[i] > min)
{
s = i;
break;
}
}
//find the first element in arr[e+1 .. n-1] which is greater than min
for (i = n - 1; i >= e + 1; --i)
{
if (arr[i] < max)
{
e = i;
break;
}
}
printf(" The unsorted subarray which makes the given array "
" sorted lies between the indees %d and %d", s, e);
return;
}
No comments:
Post a Comment