Rank of All Elements in an Array using C++

In the given problem, we need to rank all the given elements of an array, with the smallest number having the smallest rank and the largest having the largest rank. We also need to change the ranks of a number depending on their frequencies, for examples −

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

Approach to find The Solution

There are two different approaches to find the solution, and they are −

Brute Force Approach

In this approach, we will loop, select any particular element, and determine its rank.

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] << ' ';    return 0; }

Output

1.5 4 6 4 1.5 7 4

This program has a time complexity of O(N*N) where N is the size of a given array now; as you can see, our time complexity is not good, so we will increase its efficiency to work for higher constraints well.

Efficient Approach

In this approach, we are going to take a new array and sort it now as the array is sorted now we know that all the elements of the same rank will be together, so now we rank them as usual and then calculate the rank of a particular 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 approach, we sort our array, and then we rank each of the elements from the starting (ranks starting from 1). Now, if our prev element is equal to our current element, we increase s and stack up to our sum of ranks. When our elements are changed, we divide the ranks among previous elements, refresh s and total, and continue our code.

Conclusion

In this article, we solve a problem to find the Rank of all elements in an array. We also learned the C++ program for this problem and the complete approach ( Normal and efficient ) by which we solved this problem. We can write the same program in other languages such as C, java, python, and other languages.