Introduction
Problem statement
We are given an array having n elements. After Sorting the given array, our task is to count the number of misplaced elements from the index.
Sample Examples
Example 1:
Input: a[] = { 6, 2, 3, 8, 9 ,1 }
Output: 4
Explanation
Sorted array = { 1, 2, 3, 6, 8, 9 }
Index of elements {1, 6, 8, 9} are misplaced after sorting
Example 2:
Input: a[]={7, 5, 9, 3, 4}
Output: 5
Explanation
Sorted array = {3, 4, 5, 7, 9}
All elements are misplaced from their indexes.
Approach
The idea is simple, sort the given array and store it in a temporary array. Now compare all the elements of the given array from the corresponding elements of the temporary array (sorted). If the corresponding elements are not the same, count and store them in a count variable.
After comparing all the elements, return the value of the count.
Steps of algorithm
 Create a temporary array of size same as the given array, temp[n].
 Store all the elements of the given array in the temporary array.
 Sort the temporary array using the sort function, sort(temp, temp+n).
 Create a count variable and initialize it with 0, count = 0.
 Compare the elements of the given array with the elements in the temporary array. If the elements are not the same, increment the count variable by 1 (count++).
 Finally, return the value of the count.
Letâ€™s understand the above steps with an example:

Copy all the elements in the temp array.

Sort the temp array, sort(temp, temp+n)

Compare the elements.
Misplaced elements are {1, 6, 8, 9}
count = 4

Return the value of the count.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int count_misplaced(int a[], int n)
{
int temp[n];
for (int i = 0; i < n; i++)
{
temp[i] = a[i];
}
sort(temp, temp + n);
int count = 0;
for (int i = 0; i < n; i++)
{
if (temp[i] != a[i])
count++;
}
return count;
}
int main()
{
int a[] = {6, 2, 3, 8, 9 , 1};
int n = sizeof(a) / sizeof(a[0]);
cout << " Number of misplaced elements: " << count_misplaced(a, n);
return 0;
}
Output:
Number of misplaced elements: 4
Complexity Anlaysis
Time complexity: We are using a sort function to sort the temporary array, so the time complexity is O(n*logn).
Space complexity: O(n), as we are using a temporary array (temp).
Also see, Rabin Karp Algorithm.