Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Algorithm
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a subarray?
4.2.
What is the time complexity of the built in sort function?
4.3.
What is Bubble sort?
5.
Conclusion
Last Updated: Mar 27, 2024

Sorting Array Except Elements in a Subarray

Author Ankit kumar
0 upvote

Introduction

This blog will discuss the approach to Sorting an array while taking care that a particular subarray remains untouched. Before jumping on the approach to the problem, let us first understand the problem.

Problem Statement

Given an array of integers, you have to sort the array such that a particular section of the array( given ) will remain untouched. Note that the given section will not be sorted.

Sample Example

Input: arr[ ] = { 15,5,8,6,16,11 } L = 1,R = 3

 

Output: { 11,5,8,6,15,16 }

 

Since the element from L to R remains untouched and the remaining array is sorted.

Brute Force Algorithm

This problem can be solved by separating the operable area into a new memory and then sorting the elements in this new memory. Finally, we need to paste the new rearranged values to the originally given array. In this way, we can partially sort the array while letting a given section of the array be untouched.

Steps of Algorithm

Step 1: Sort the first left part of the array as in bubble sort.

Step 2: Inside the for loop, separately sort the array left and right operable part.

Step 3: Sort the right part of the array.

Step 4: Inside the for loop, separately sort the array left and right operable part.

Step 5: Print the resultant array.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//Function to partially sort the array
void partialSortFunc(int &arr[],int size,int L,int R){
    int i,j;
    //sorting the first left part
    for(i = 0;i<L;i++){
        for(j = i+1;j<L;j++){
            if(arr[i] > arr[j])
            swap(arr[i],arr[j]);
        }
        for(j = R+1;j<size;j++){
            if(arr[i] > arr[j])
            swap(arr[i],arr[j]);
        }
    }
    //sorting the right part
    for(i = R+1;i<size;i++){
        for(j = i+1;j<size;j++){
            if(arr[i] > arr[j])
            swap(arr[i],arr[j]);
        }
    }
}

int main(){
    int arr[] = { 15,5,8,6,16,11 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    int L = 1,R = 3;
    
    //Calling the partial sort function
    partialSortFunc(arr,size,L,R);
    
    //Print the resultant array
    for(int i = 0;i<size;i++){
        cout<<arr[i]<<" "; 
    }
}

 

Output:

 {11,5,8,6,15,16}

 

Complexity Analysis

Time complexity: O(n^2)

Since two for loops are running in a nested way with O(n) time complexity,therefore the total time complexity would be O(n*n) ,i.e, O(n^2).

Space complexity: O(1)

As no extra space is required apart from the given space,therefore total space complexity would be constant.

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

Optimized Approach

Let us discuss the optimized approach for sorting the array such that the given subarray remains untouched.

Steps of Algorithm

Step 1: Create a whole new array of size = arr.size - ( R-L+1 ).

Step 2: Copy all the elements from the given array to the new array except the given section.

Step 3: Sort the new array.

Step 4: Copy elements from the new array to the given old array except in the index range (L,R).

Step 5: Print the array.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//Function to partially sort the array
void partialSortFunc(int &arr[],int size,int L,int R){
    //calculating the size of new array
    int newSize = size-L+R-1;
    //creating the new array
    int newArr[newSize];
    int i;
    //copying elements from given array to new array
    for(i = 0;i<L;i++){
        newArr[i] = arr[i];
    }
    for(i = R+1;i<size;i++){
        newArr[L + i-(R+1)] = arr[i];
    }
    //sorting the new array
    sort(newArr,newArr+newSize);
    //copying back from new array to array
    for(i = 0;i<L;i++){
        arr[i] = newArr[i];
    }
    for(i = R+1;i<size;i++){
        arr[i] = newArr[L + i-(R+1)];
    }
}

int main(){
    int arr[] = { 15,5,8,6,16,11 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    int L = 1,R = 3;
    
    //Calling the partial sort function
    partialSortFunc(arr,size,L,R);
    
    //Print the resultant array
    for(int i = 0;i<size;i++){
        cout<<arr[i]<<" "; 
    }
}

 

Output: 

{11,5,8,6,15,16}

 

Complexity Analysis

Time complexity: O(nlogn)

Since the sort function requires O(nlogn) time while copying the array to a new array takes O(n) time, therefore, the overall time complexity is O(nlogn).

Space complexity: O(n)

As an extra array is required in this approach apart from the given array which is of the order of n.Therefore space complexity will be of order O(n).

Frequently Asked Questions

What is a subarray?

The array inside the array is called a subarray. A subarray is a continuous section inside the array. Unlike a subset, it is not discrete; rather, it is continuous.

What is the time complexity of the built in sort function?

The time complexity of the built-in sort function is nlogn since most of the languages use timsort, which is a hybrid combination of merge sort and insertion sort.

What is Bubble sort?

Bubble sort is the simplest sorting algorithm that sorts the array by comparing each and every pair and swapping if they are not in order.Time complexity of bubble sort is O(n^2).

Conclusion

This article discussed the approach of partially sorting the array with a given section left untouched. In this approach, the operable elements get copied to a new array and get sorted there. Finally, the new array elements get pasted in the previous array.

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Sort rows in ascending order followed by columns in descending
Next article
Count minimum steps to get the desired array
Live masterclass