The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subarray

A subarray is a continuous part of an array. In other-words, a subarray is an array that is inside another array.

In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

For example, in the array [1, 2, 3, 4], there are 10 non-empty sub-arrays, which are:

[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4]

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

Reversing a Subarray (or Array)

While the left pointer is less than the right pointer, swap the elements at their two positions. After each swap, increment the left pointer and decrement the right pointer to move towards the center of the array. This procedure will swap all the elements in the first array half with their corresponding elements in the second half.

If the number of elements in the subarray (or array) is odd, then the center element will not be swapped. If the number of elements in the subarray (or array) is even, then the two center elements will be swapped.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable. This module of the full course deals only with fixed size windows. With fixed size window, the size of the last window can be less than the size of each of the previous windows.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an array of N numbers where a subarray is sorted in descending order and the rest of the numbers in the array are in ascending order, the task is to sort the whole array.

Examples:

Input: {2, 5, 65, 55, 50, 70, 90}
Output: {2, 5, 50, 55, 65, 70, 90}
The subarray from 3rd position to 5th position was in reverse order.

Input: {1, 7, 6, 5, 4, 3, 2, 8}
Output: {1, 2, 3, 4, 5, 6, 7, 8}
The subarray from 2nd position to 7th position was in reverse order.

There is only one descending subarray in the expected ascending array (in both examples).

Recommended Approach in O(n.log n) Time

This approach uses a commercial sorting function to sort the whole array in at least O(n.log n) time. Since sorting has not yet been taught in this full course yet, this approach is not addressed any further in this document.

It is possible to have this particular type of whole array sorted, in O(n) time; see below.

Smarter Approach in O(n) Time

It must be stressed here that, this smarter approach works only with this particular type of unsorted array. For a random unsorted array, use a commercial sorting function.

Strategy

Find and store the starting and ending indexes of the reversed subarray. This takes O(n) time though it is hardly up to O(n) time in many different arrays.

Since the subarray is in descending order and the rest of the elements are in ascending order, just reverse the subarray, and the whole array will be sorted. Use two-pointers technique to reverse the subarray.

Reversing a subarray using two-pointers technique takes O(½M) time, where M is the length of the subarray. This is officially quoted as O(n) time.

So finding and storing the start and end index of the subarray, plus reversing the subarray, may be said to be taking O(2n) time, though it will hardly be up to that, in many different arrays. Since the coefficient (multiplier of ½, 2, 3, etc.) in front of n is normally omitted, the official time complexity of this smarter approach for this particular sorting problem, is quoted as O(n).

Smarter Approach Program

The smarter approach program is (read through the code and comments):

#include <stdio.h>

void printSorted(int A[], int n) {
    //initialization for subarray pointers
    int left = -1, right = -1;    

    // find the starting index of subarray
    for (int i = 1; i < n; i++) {
        if (A[i] < A[i - 1]) {
            left = i - 1;
            break;
        }
    }

    // find the ending index of subarray
    for (int i = n - 2; i >= 0; i--) {
        if (A[i] > A[i + 1]) {
            right = i + 1;
            break;
        }
    }

    // if no reversed subarray is present
    if (left == -1 && right == -1) {
        for (int i = 0; i < n; i++)    //edge case, given array already sorted 
            printf("%i, ", A[i]);    //not included in time complexity
        return;
    }

    // swap the reversed subarray
    while (left < right) {

        // swaps the left and right elements
        int temp = A[right];
        A[right] = A[left];
        A[left] = temp;
        left++;
        right--;
    }
    
    //now print whole sorted array
    for (int i = 0; i < n; i++)    //not included in time complexity
        printf("%i, ", A[i]);

    printf("\n");    //go to next line for next test case
}

int main(int argc, char **argv) {
    int A[] = {2, 5, 65, 55, 50, 70, 90};
    int n = sizeof(A) / sizeof(A[0]);
    
    printSorted(A, n);
    
    
    int A2[] = {1, 7, 6, 5, 4, 3, 2, 8};
    int n2 = sizeof(A2) / sizeof(A2[0]);
    
    printSorted(A2, n2);
        
    return 0;
}

The output is:

    2, 5, 50, 55, 65, 70, 90, 
    1, 2, 3, 4, 5, 6, 7, 8, 

as expected.

The space complexity is O(n) for the same array in the calling and called functions.

Thanks for reading.