- Write a program in C to find smallest unsorted array such that sorting this array makes whole array sorted.

Given an integer array of size N, we have to **find smallest unsorted subarray, sorting which will make whole of input array sorted**. If input array is already sorted then no sub subarray exists whereas if array is sorted in decreasing order then we have to sort whole input array. For Example :

Input Array : [1 3 4 6 5 2 11 7 10 14 15 16] Unsorted sub-Array is from index 1 to 8 Input Array : [1 2 3 4 7 6 5 8 9 10] Unsorted sub-Array is from index 4 to 6

Let inputArray be a sorted integer array of size N.

**Algorithm to find smallest unsorted subarray.**

- Traverse inputArray from index 0 to N-1 and find first element which is greater than it's next element. Let this index be leftIndex (inputArray[leftIndex] > inputArray[leftIndex+1]).
- If leftIndex >= N-1, then whole array is already sorted.
- Traverse inputArray from index N-1 to 0 and find first element which is smaller than it's next element. Let this index be rightIndex (inputArray[rightIndex] < inputArray[rightIndex -1])
- Now find the minimum and maximum element of subarray from index leftIndex to rightIndex. Let it be min and max.
- Traverse inputArray from index N-1 to rightIndex and find first element smaller than max. Let this index be rightMostIndex.
- Traverse inputArray from index 0 to leftIndex and find first element larger than min. Let this index be leftMostIndex.
- Required subarray is from index rightMostIndex to leftMostIndex.

## C program to find smallest unsorted subarray to make whole array sorted

#include <stdio.h> void findUnsortedSubArray(int *array, int size) { int i, left, right, min, max; /* traverse from left to right and find first element which is greater than next element */ for(left = 0; left < size-1; left++) { if (array[left] > array[left+1]) break; } /* If left == size-1, then whole array is already sorted */ if(left == size-1) { printf("Array is already sorted"); return; } /* traverse from right to left and find first element which is smaller than next element */ for(right = size-1; right > 0; right--){ if(array[right] < array[right-1]) break; } /* Now find the maximum and minimum element of sub array from index left to right */ max = array[left]; min = array[right]; for(i = left+1; i <= right; i++) { if(array[i] < min) min = array[i]; if(array[i] > max) max = array[i]; } /* Traverse from right to left and find first element which is smaller than max */ for(i = size-1; i >= right+1; i--) { if(array[i] < max) { right = i; break; } } /* Traverse from left to right and find first element which is greater than min */ for(i = 0; i < left; i++) { if(array[i] > min) { left = i; break; } } printf("\nUnsorted sub-Array is from index %d to %d", left, right); return; } int main(){ int array[12] = {1, 3, 4, 6, 5, 2, 11, 7, 10, 14, 15, 16}; int i; for(i = 0; i < 12; i++){ printf("%d ", array[i]); } findUnsortedSubArray(array, 12); return 0; }Output

1 3 4 6 5 2 11 7 10 14 15 16 Unsorted sub-Array is from index 1 to 8