Wednesday, 5 November 2014

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

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


}

No comments:

Post a Comment