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 Examples
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Anlaysis
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Program to find the number of misplaced elements from the index after sorting

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

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

Frequently Asked Questions

Q1. What are the benefits of sorting and indexing?

Answer: Data organisation can be a useful analytical tool in and of itself, bringing patterns and anomalies to light. Sorting a table physically reorders data and outputs the results to a new Analytics table. The underlying physical order of data is not changed by indexing.

 

Q2. Which sorting method is the most effective?

Answer: Quicksort is one of the most efficient sorting algorithms, and as a result, it is also one of the most popular. The first step is to choose a pivot number. This number will separate the data, with smaller numbers on the left and larger numbers on the right.

 

Q3. What can we do to make merge sort better?

Answer: For small subarrays, use insertion sort. Most recursive algorithms can be improved by treating small cases differently. For small subarrays, switching to insertion sort will reduce the running time of a typical mergesort implementation by 10% to 15%. Check if the array is already in the correct order.

Key Takeaways

This article discussed the approach to finding the number of misplaced elements from the index after sorting using a temporary array with examples to understand its C++ code better.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Recommended Problem - Merge K Sorted Arrays

Thank you for reading!

Live masterclass