Sub Sort

In this approach, we consider every possible subarray that can be formed from the given array ‘ARR’. For every subarray ARR[i … j] considered, we need to check whether this is the smallest unsorted subarray or not.

 

The algorithm is as follows:

1. Let’s take the variable ‘ANS’ equal to 'N' (the length of the array) initially.
2. Now for every subarray ARR[i … j], we will find the maximum and minimum value lying in that subarray given by ‘MAXELEMENT’ and ‘MINELEMENT’ respectively.
3. Further, we have to check that every element in ARR[0 … i-1] should be lesser than the ‘MINELEMENT’.
4. And similarly every element in ARR[j+1 …. N-1] should be greater than the ‘MAXELEMENT’.
5. The above two steps are performed to check whether the subarray ARR[0 … i-1] and subarray ARR[j+1 … N-1] are sorted because then only ARR[i ... j] could be our required subarray.
6. If all conditions are met, then ('j' - 'i' + 1) will be the required length.
7. The same process will be repeated for every subarray chosen and the smallest unsorted subarray is determined.

This approach is based on the idea of selection sort. But instead of swapping as we do in the case of selection sort, we will determine the leftmost boundary of the unsorted array and the rightmost boundary of the unsorted subarray.

The algorithm is as follows:

1. Let’s take two variables ‘START’ and ‘END’ where ‘START’ will be the leftmost boundary of the unsorted subarray and the ‘END’ will be the rightmost boundary of the unsorted subarray.
2. Here we will use two nested for loops where the outer loop starts from ‘i’ = 0 to ‘i’ = length of array - 2  and inner loop traverses from ‘j’ = ‘i’ + 1 to ‘j’ = length of array - 1.
3. Now for every ‘ARR[i]’, we will check if any of ‘ARR[j]’ is less than that of ‘ARR[i]’, which means both ‘ARR[i]’ and ‘ARR[j]’ are not at their correct sorted position.
4. The position of ‘ARR[i]’ (that is i) and ‘ARR[j]’ (that is j) will now mark the boundary of the unsorted array for the time being.
5. Now after considering all the ‘ARR[i]’ we will take the leftmost ith index which is not at its correct position.
6. And similarly out of all ‘ARR[j]’ for each of ‘ARR[i]’ we will take the rightmost jth index which is not at its correct position.
7. It will be achieved by ‘START’ = min('START' , ‘i’) and ‘END’ = max('END' , ‘j’) if ('ARR[j]' < 'ARR[i]').
8. Finally return the answer as ('END' - ‘START’ + 1) if ('END' >= ‘START’) otherwise return 0.

This approach is based on the idea of sorting. Here we will copy the given array in another array and then sort it and then compare this array with the given array. We will determine the leftmost and the rightmost position, where the element at this position mismatches. And the subarray lying between these two positions is the unsorted subarray.

The algorithm is as follows:

1. Make an array ‘COPY’ of the same size as that of the original array and copy all the elements from array ‘ARR’ into array ‘COPY’.
2. Next sort the array ‘COPY’ in ascending order.
3. Take two variables ‘START’ = length of the array and ‘END’ = 0.
4. Now traverse the array ‘COPY’ and whenever there is a mismatch between the elements of array ‘ARR’ and array ‘COPY’, then ‘START’ = min('START', ‘i’) and ‘END’ = max('END', ‘i’).
5. The ‘START’ and the ‘END’ variables mark the leftmost and the rightmost indices of the unsorted subarray.
6. Then finally return the answer, if ('END' > ‘START’) return ('END' - ‘START’ + 1), otherwise return 0.

This approach uses two passes of the array. In the first pass, Iterate from the end, and check whether the array is in descending order, i.e., ARR[i] > ARR[i-1] > ARR[i-2] > … . If not we will find the minimum index at which the condition breaks. In the second pass, Iterate from the start, and check whether the array is in ascending order, i.e., ARR[i] < ARR[i+1] < ARR[i+2] < …. If not we find the maximum index at which the condition breaks.

The algorithm is as follows:

1. Create a ‘START’ and ‘END’ variable to store the indexes of starting and ending positions of the shortest unsorted contiguous subarray respectively.
2. Make a variable ‘CURMIN’ and initialize it with an infinite value.
3. Iterate from the end of the array, and check whether the element at index ‘i’  is less than ‘curMin’ or not.
   • If it is less than ‘CURMIN’, then update ‘CURMIN’ to this ‘ARR[i]’.
   • Else, update ‘START’ to ‘i’.
4. Make a variable ‘CURMAX’ and initialize it with a negative infinite value.
5. Iterate from the start of the array, and check whether the element at index ‘i’ is greater than 'CURMAX' or not.
   • If it is more than ‘CURMAX’, then update ‘CURMAX’ to this ‘ARR[i]’.
   • Else, update ‘END’ to ‘i’.
6. In the end check for a valid start index, which means if ('START' == -1) then return 0 otherwise return ('END' - ‘START’ + 1).

Example:

Let's say we have an array ARR = {2, 6, 4, 8,10,9,15} (consider 0 based indexing).

Here n = 7 , start = -1 , end = n

Also curMin = inf curMax = -inf

Now first traverse the array from right to left we have two conditions:

First:  if(curMin > Arr[i]) then curMin = Arr[i] 

Second: if(Arr[i] > curMin) then update start = i 

For i = 6 (Arr[6] = 15) :

curMin = 15

start = -1 

For i = 5 (Arr[5] = 9) :

curMin = 9

start = -1 

For i = 4 (Arr[4] = 10) :

curMin = 15

start = 4

For i = 3 (Arr[3] = 8) :

curMin = 8

start = 4

For i = 2 (Arr[2] = 4) :

curMin = 4

start = 4

For i = 1 (Arr[1] = 6) :

curMin = 4

start = 1

For i = 0 (Arr[0] = 2) :

curMin = 2

start = 1 

Now traverse the array from left to right we have two conditions:

First:  if(curMax < Arr[i]) then curMax = Arr[i] 

Second: if(Arr[i] < curMax) then end = i 

For i = 0 (Arr[0] = 2) :

curMax = 2

end = 7 

For i = 1 (Arr[1] = 6) :

curMax = 6

end = 7 

For i = 2 (Arr[2] = 4) :

curMax = 6

end = 2

For i = 3 (Arr[3] = 8) :

curMax = 8

end = 2

For i = 4 (Arr[4] = 10) :

curMax = 10

end = 2

For i = 5 (Arr[5] = 9) :

curMax = 10

end = 5

For i = 6 (Arr[6] = 15) :

curMax = 15

end = 5

At the end, we have ‘start’ = 1 and ‘end’ = 5 

Hence subarray will be { 6, 4, 8,10,9}