Program to Find the Smallest Unsorted Subarray such that Sorting it Makes Whole Array Sorted

  • 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
Posted by
Labels: ,