Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Efficient Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.3.1.
Output
4.4.
Implementation in Java
4.4.1.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is an Array?
5.2.
Which is the fastest sorting technique?
5.3.
What is the best time complexity for solving the creative sorting problem?
5.4.
What is the time complexity of mergesort?
5.5.
What is the underlying algorithm of the sort() function in C++?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Creative Sorting problem

Author Sahil Setia
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Hey Ninjas! An essential subject for programming interviews is the Array. You'll discover that arrays are used in numerous problems, from complex to easy ones. Sorting is one of the crucial topics in data structure and algorithms. It is used to order the items specifically, and many other algorithms require sorting to function efficiently. There are many sorting algorithms like bubble sortquick sort, and merge sort.

title image

In this blog, we will discuss the creative sorting problem and the approach to solving the problem. Before diving into the solution, let’s discuss the problem statement briefly.

Problem Statement

Given an array consisting of integers. The main task is to find the largest sub-array in the given array, which is sorted. But, if the given array is not sorted, our task is to divide the array into halves (exactly from between) and check the corresponding two halves for sorting.

We aim to find the length of the largest sorted array possible from the given unsorted array with the condition mentioned.

Input

Total Number of elements in the array(N) = 8

Array = [1, 2, 9, 8, 4, 6, 8, 7]

Output

2

Explanation

Sorted subarrays possible when continuously dividing the arrays into halves are [1,2], and [4, 6]. Since the maximum size of sorted subarrays is 2, the answer to the input sample is 2.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Dry run image 1

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.

Dry run image 2

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

Dry run image 3

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

Dry run image 4

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

Dry run image 5

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

Dry run image

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

Dry run image

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

Dry run image

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

output image

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

output image

Time Complexity

O(N2where ‘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(N2).

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

Dry Run Image

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

output image

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

output image

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:

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!

Previous article
Create Arithmetic Progressions in the Array
Next article
Find the Minimum Length Unsorted Subarray, Sorting Which Makes the Complete Array Sorted
Live masterclass