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.
85+ registered