Ranking of array element sorting written in C++

In the given problem, we need to rank all the given elements of the array, the smallest number has the smallest rank and the largest one has the largest rank. For example, we also need to change the ranking of numbers based on their frequency -

Input : 20 30 10
Output : 2.0 3.0 1.0

Input : 10 12 15 12 10 25 12
Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0

Here the rank of 10 is 1.5 because there are two 10s present in the given array now if we assume they both take different ranks i.e. 1 and 2 and we thus divide it within themselves so their rank becomes 1.5 and 1.5.

Input : 1, 2, 5, 2, 1, 60, 3
Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

Methods of finding the solution

There are two different ways to find the solution, they are-

Brute Force Method

In this method we will loop, select any particular element and determine its ranking.

Example

#include <bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 25, 2}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array

   float rank[n] = {0}; // our ranking array
   for (int i = 0; i < n; i++) {
      int r = 1; // the number of elements greater than arr[i]
      int s = 1; // the number of elements equal to arr[i]

      for (int j = 0; j < n; j++) {
         if (j != i && arr[j] < arr[i])
            r += 1;
   
         if (j != i && arr[j] == arr[i])
            s += 1;
      }
      rank[i] = r + (float)(s - 1) / (float) 2; // using formula
      //to obtain rank of particular element

   }

   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rank[i] << &#39; &#39;;

   return 0;
}

Output

1.5 4 6 4 1.5 7 4

The time complexity of this program is O(N*N), where N is the given array now size; as you can see, our time complexity is not good, so we will increase its efficiency to fit better with higher constraints.

Efficient method

In this method we will take a new array and sort it, since the array is sorted, now we know that all the elements with the same rank will be together, so Now we rank them as usual and then calculate the rank of the specific element.

Example

#include <bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 60, 3}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array
   float rank[n] = {0}; // our ranking array
   int old[n];
   for(int i = 0; i < n; i++)
   old[i] = arr[i];
   sort(arr, arr+n); // sorting the array
   int prev = arr[0];
   int r = 1; // ranks
   int s = 0; // frequency
   int tot = 0; // will stack up all the rank contained by an element
   map<int, float> rrank;

   for (int i = 0; i < n; i++) {
      if(prev == arr[i]) {
         s++;
         tot += r;
      } else {
         float now = 0;
         now = (float)tot/s; // dividing the ranks equally
         rrank[prev] = now;
         prev = arr[i];
         tot = r;
         s = 1;
      }
      r++;
   }
   rrank[arr[n-1]] = (float)tot/s;
   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rrank[old[i]] << " ";

   return 0;
}

Output

1.5 3.5 6 3.5 1.5 7 5

Explanation of the above code

In this method, we sort the array and then start from the beginning for each Elements are ranked (ranking starts from 1). Now, if our previous element is equal to the current element, we increment s and add to our rank sum. When our element changes, we separate the previous element's ranks, refresh s and the total, and continue with our code.

Conclusion

In this article, we solved a problem to find the ranking of all elements in an array. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages, such as C, java, python and other languages.

The above is the detailed content of Ranking of array element sorting written in C++. For more information, please follow other related articles on the PHP Chinese website!