Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Find the misplaced elements

Last Updated on June 17, 2022 by Ria Pathak

Sorting

Easy

### Problem Statement (Simplified):

Find how many elements change their place after sorting array.

See original problem statement here

#### Test case:

``````Input:
1
5
8 4 2 1 9

Output:
4

Explanation:
On sorting array, the array becomes [1 2 4 8 9] and we can see 1,2,4 and 8 have a different places in the given array. So 4 is our answer.``````

### Solving Approach :

Observation: We can see that size of array can go from 1 to `10`6, in worse conditions let the size of the array be `10`6 if we sort this array using any of sorting techniques i.e. Bubble Sort, Insertion Sort, Selection sort. They all take O(`N`2) in worst cases, which results in `10`12 iterations when the size of the array is `10`6. So we, can’t choose the above three sorting algorithms. We use Merge Sort to sort array as it sorts array in linearithmic time complexity (`N x log(N)`) where N is size of array.

• We make a duplicate array, which will be sorted. After sorting we count number of elements which differe at same index.

#### Example:

Let array `A` be,

We need to find how many elements stays at their place after sorting, So we maintain a `Secondary Array` which is copy of our primary arra.

After Sorting `Secondary Array`, `Secondary Array` becomes

Now, we compare both arrays, element by element and count array elements which are different at same index in both arrays.

Here, we can see `5` and `1` are not at their same place, so our answer is `2`.

### Solutions:

```
#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{
int test;
scanf("%d",&test);

while(test--){
int n;
scanf("%d",&n);

int arr[n];
int sorted[n];
for(int i=0; i<n; i++){
scanf("%d",&arr[i]);
sorted[i] = arr[i];
}

//Sorting array
mergeSort(sorted,0,n-1);
int count = 0;

for(int i=0; i<n; i++)
if(arr[i]!=sorted[i])
count++;
printf("%d\n",count);
}
}
```
```#include <bits/stdc++.h>
using namespace std;

void merge(int arr[], int start, int mid, int end){
int left[mid-start+1]={0};
int right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{
int test;
cin>>test;

while(test--){
int n;
cin>>n;

int arr[n];
int sorted[n];
for(int i=0; i<n; i++){
cin>>arr[i];
sorted[i] = arr[i];
}

//Sorting array
mergeSort(sorted,0,n-1);
int count = 0;

for(int i=0; i<n; i++)
if(arr[i]!=sorted[i])
count++;
cout<<count<<endl;
}
}
```
```import java.util.*;
import java.io.*;

public class Main {
static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int test = sc.nextInt();

while(test--!=0){
int n = sc.nextInt();
int arr[] = new int[n];
int sorted[] = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
sorted[i] = arr[i];
}

//Sorting array
mergeSort(sorted,0,n-1);
int count = 0;

for(int i=0; i<n; i++)
if(arr[i]!=sorted[i])
count++;
System.out.println(count);
}

}
}
```
```def merge(arr, start, mid, end):
left = [0 for i in range(mid - start + 1)]
right = [0 for i in range(end - mid)]

for i in range(start, mid + 1):
left[i - start] =  arr[i]

for i in range(mid + 1, end + 1):
right[i - (mid + 1)] = arr[i]

leftIndex = 0
rightIndex = 0
arrIndex = start

while leftIndex <= mid - start and rightIndex < end - mid:

if(left[leftIndex] < right[rightIndex]):
arr[arrIndex] = left[leftIndex]
leftIndex += 1

else:
arr[arrIndex] = right[rightIndex]
rightIndex += 1

arrIndex += 1

while(leftIndex <= mid - start):
arr[arrIndex] = left[leftIndex]
leftIndex += 1
arrIndex += 1

while(rightIndex < end - mid):
arr[arrIndex] = right[rightIndex]
rightIndex += 1
arrIndex += 1

def mergeSort(arr, start, end):
if(end == start):
return
mergeSort(arr, start, (start + end) // 2)
mergeSort(arr, ((start + end) // 2) + 1, end)
merge(arr, start, (start + end) // 2, end)

for _ in range(int(input())):

n = int(input())
arr = list(map(int, input().split()))
sorted = arr.copy()
mergeSort(sorted, 0, n - 1)
count = 0

for i in range(n):
if arr[i] != sorted[i]:
count += 1

print(count)
```

[forminator_quiz id="1075"]

So, in this blog, we have tried to explain how many elements change their place after sorting array. If you want to solve more questions on Sorting, which are curated by our expert mentors at PrepBytes, you can follow this link Sorting.