Creative Sorting problem

Brute Force Approach

This is a straightforward and naive approach. It is possible to recursively divide an array and check whether each sub-array is sorted. If so, we give the length of the sub-array. If the parent subarray is sorted then the length of the current subarray is returned else the maximum value of each recursive function's left and right half subarrays is returned.  Let’s take a look at the algorithm of the brute force approach.

Algorithm

1. Call the ‘max_sorted_subarray()’ function, which calculates the maximum sorted subarray by following the creative sort algorithm.
    
2. For the range [left, right] check if the subarray is sorted or not using the ‘is_sorted()’ function. If sorted, return the current size of the subarray. Else, call the ‘max_sorted_subarray()’ for the left half and right half.
    
3. Return the maximum of the answer of the left half and right half and display the result as the output.

Dry Run

The given array looks like this.

The first call is made to the whole array from index 0 to index 8, and it is checked whether the array is sorted or not.

As the current array is not sorted, the left and right halves are considered separately. The left half looks like this-

The second call is made to the subarray from index 0 to index 4 and is checked whether the array is sorted.

As the current array is not sorted the left and right halves are considered separately. The left half looks like this-

As the current subarray is sorted. Hence, 2 is returned from this recursive call which is the size of the current subarray.

The previous right half of the subarray is considered now, which looks like this.

As the current subarray is not sorted, the left and right halves are considered separately.

The left and right halves of this subarray contain a single element which is always sorted as the single element subarray is always sorted.

Similarly, like this, the recursive call occurs. Each time we get a subarray that is not sorted. The corresponding left, and right halves of the subarray are called and checked. Overall, after all, iterations, the answer for this array is 2.

Must Read Algorithm Types

Implementation in C++

#include <iostream>
#include <vector>

using namespace std;

/*
    Function which checks if [left, right] 
    of array is sorted or not
*/
bool is_sorted(vector <int>& arr,int left, int right){
    
    for(int i=left+1;i<right;i++){
        
        // Current element less than previous element
        if(arr[i] - arr[i-1] < 0){
            return false;
        }
    }
    
    return true;
}

// Function which returns maximum length of sorted subarray
int max_sorted_subarray(vector <int>& arr,int left,int right){
    
    // When the array is sorted
    if(is_sorted(arr,left,right)){
        
        return (right-left);
    }
    
    int mid = (left + right) / 2;
    
    // Evaluating maximum of the two halves subarrays
    int lmax = max_sorted_subarray(arr,left,mid);
    int rmax = max_sorted_subarray(arr,mid,right);
    
    // Return the maximum of the two
    return max(lmax,rmax);
}

int main() {
    
    // Total number of elements in the array
    int N = 8;
    
    // Given elements of the array
    vector <int> arr(N);
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 9;
    arr[3] = 8;
    arr[4] = 4;
    arr[5] = 6;
    arr[6] = 8;
    arr[7] = 7;
    
    // Calling the function and displaying the output
    cout<<max_sorted_subarray(arr,0,N);
}

Output

Implementation in Java

public class MyClass {
    
    /*
        Function which checks if [left, right] 
        of array is sorted or not
    */
    static boolean is_sorted(int arr[],int left, int right){
        
        for(int i=left+1;i<right;i++){
            
            // Current element less than previous element
            if(arr[i] - arr[i-1] < 0){
                return false;
            }
        }
        
        return true;
    }
    
    // Function which returns maximum length of sorted subarray
    static int max_sorted_subarray(int arr[],int left,int right){
        
        // When the array is sorted
        if(is_sorted(arr,left,right)==true){
            
            return (right-left);
        }
        
        int mid = (left + right) / 2;
        
        // Evaluating maximum of the two halves subarrays
        int lmax = max_sorted_subarray(arr,left,mid);
        int rmax = max_sorted_subarray(arr,mid,right);
        
        // Return the maximum of the two
        return Math.max(lmax,rmax);
    }

    public static void main(String args[]) {
        
        // Total number of elements in the array
        int N = 8;
        
        // Given elements of the array
        int arr[] = new int [N];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 9;
        arr[3] = 8;
        arr[4] = 4;
        arr[5] = 6;
        arr[6] = 8;
        arr[7] = 7;
        
        // Calling the function and displaying the output
        System.out.print(max_sorted_subarray(arr,0,N));
    }
}

Output

Time Complexity

O(N²) where ‘N’ is the total number of elements in the array

Explanation: In the worst case, on the last level there will be N recursive calls, and on the second level there will be N/2 recursive calls, and so on. The summation of N + N/2 + N/4 + .. up to infinite terms. The sum of these series is O(N). So, the recursive calls have a time complexity of O(N) and on each call, there will be an ‘is_sorted()’ function with a time complexity of O(N). Hence, the overall time complexity will be O(N²).

Space Complexity

O(1)

Explanation: The auxiliary space complexity of the code is O(1) as there is no extra space used apart from the recursive calls, which are constant in space.

Efficient Approach

The problem is resolved using the merging technique of merge sort and recursion. Since an array of size one is already sorted, we may solve this issue by recursively splitting the current array in half and returning 1.

The function returns the length of the greatest sorted sub-array for each iteration. If the lengths of both sub-arrays are equal, we determine whether the left subarray's final element is smaller than the right subarray's opening element. We can observe that sub-arrays and the parent array are sorted under the above-mentioned circumstances. Thus, we give the length of the parent array.

If not, we compare the lengths from the two sub-arrays and return the longest possible length.

Algorithm

1. Call the ‘max_sorted_subarray()’ function, which calculates the maximum sorted subarray by following the creative sort algorithm.
    
2. If the left and the right difference is one, then return one as the array is of a single element.
    
3. Otherwise, store the answer for the left half in ‘lmax’ and the answer for the right half in ‘rmax’.
    
4. If the ‘lmax’ plus ‘rmax’ is equal to the size of the current subarray and arr[mid-1] is less than equal to arr[mid], then return the sum of ‘lmax’ and ‘rmax’.
    
5.  Return the maximum of the ‘lmax’ and ‘rmax’.
    
6. Return the maximum answer of the left half and right half and display the result as the output.

Dry Run

Implementation in C++

#include <iostream>
#include <vector>

using namespace std;

// Function which returns the maximum length of the sorted subarray
int max_sorted_subarray(vector <int>& arr,int left,int right){
    
    // When the array length is 1
    if(left == right - 1){
        return 1;
    }
    
    // Evaluating the middle index
    int mid = (left + right) / 2;
    
    // Evaluating the maximum of the two halves subarrays
    int lmax = max_sorted_subarray(arr,left,mid);
    int rmax = max_sorted_subarray(arr,mid,right);
    
    // Length of the current array
    int len = right - left;
    
    /*
        Condition to check if the whole 
        array from left to right is sorted.
    */
    if(lmax + rmax == len && arr[mid-1] <= arr[mid]){
        
        return lmax + rmax;
    }
    
    // Return a maximum of the two
    return max(lmax,rmax);
}

int main() {
    
    // Total number of elements in the array
    int N = 8;
    
    // Given elements of the array
    vector <int> arr(N);
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 9;
    arr[3] = 8;
    arr[4] = 4;
    arr[5] = 6;
    arr[6] = 8;
    arr[7] = 7;
    
    // Calling the function and displaying the output
    cout<<max_sorted_subarray(arr,0,N);
}

Output

Implementation in Java

public class MyClass {
    
    // Function which returns the maximum length of the sorted subarray
    static int max_sorted_subarray(int arr[],int left,int right){
        
        // When the array length is 1
        if(left == right - 1){
            return 1;
        }
        
        // Evaluating the middle index
        int mid = (left + right) / 2;
        
        // Evaluating the maximum of the two halves subarrays
        int lmax = max_sorted_subarray(arr,left,mid);
        int rmax = max_sorted_subarray(arr,mid,right);
        
        // Length of the current array
        int len = right - left;
        
        /*
            Condition to check if the whole 
            array from left to right is sorted.
        */
        if(lmax + rmax == len && arr[mid-1] <= arr[mid]){
            
            return lmax + rmax;
        }
        
        // Return a maximum of the two
        return Math.max(lmax,rmax);
    }

    public static void main(String args[]) {
        
        // Total number of elements in the array
        int N = 8;
        
        // Given elements of the array
        int arr[] = new int [N];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 9;
        arr[3] = 8;
        arr[4] = 4;
        arr[5] = 6;
        arr[6] = 8;
        arr[7] = 7;
        
        // Calling the function and displaying the output
        System.out.print(max_sorted_subarray(arr,0,N));
    }
}

Output

Time Complexity

O(N), where N is the total number of elements in the array

Explanation: In the worst case, on the last level there will be N recursive calls, on the second level there will be N/2 recursive calls, and so on. The summation of N + N/2 + N/4 + .. up to infinite terms. The sum of these series is O(N). So, the recursive calls have a time complexity of O(N).

Space Complexity

O(1)

Explanation: The auxiliary space complexity of the code is O(1) as there is no extra space used apart from the recursive calls which are constant in space.

Frequently Asked Questions

What is an Array?

An array is a data structure that sequentially stores an element of the same data type. In C/C++ or any other programming language, an array is a collection of similar data items. The data items are always stored in an array at contiguous memory locations.

Which is the fastest sorting technique?

Quicksort is considered the quickest sorting algorithm because its time complexity is O( N log N) in the best and almost average case scenarios, and in the worst case, it goes up to O (N ^ 2). Thus, it has the upper hand in most cases.

What is the best time complexity for solving the creative sorting problem?

The best time complexity for solving the creative sorting problem is O(N), where N is the total number of elements in the array.

What is the time complexity of mergesort?

The worst-case and average time complexity of mergesort is O(N*log(N)). 

What is the underlying algorithm of the sort() function in C++?

The sort() function uses IntroSort. IntroSort is a hybrid sorting technique that uses Quicksort, Heapsort, and Insertion sort to minimize the running time.

Conclusion

Sorting algorithms are important as searching elements in a sorted array becomes easier than in an unsorted array. Overall, the time complexity of searching for an element is significantly reduced, which plays an essential role in programming. Some real-life applications of sorting algorithms are a contact list on your phone, a music playlist on your phone, and so on.

In this blog, we discussed the topic of the counting sort algorithm and the working of the algorithm. We also implemented the algorithm in two different languages C++ and Java. Sorting algorithms are also an essential topic in view of interview preparations and placement. It is, therefore, imperative to become an expert with sorting algorithms, understand what goes underneath the hood, and where you can apply your learnings.

Recommended Reading:

• Bubble sort algorithm
• Understanding Heap Sort
• Bucket Sort
• Understanding QuickSort
   

Do check out the Interview guide for Product Based Companies, as well as some of the popular interview problems asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!