Classement du tri des éléments du tableau écrit en C++

Dans le problème donné, nous devons classer tous les éléments donnés du tableau, le plus petit nombre a le plus petit rang et le plus grand a le plus grand rang. Par exemple, nous devons également modifier le classement des nombres en fonction de leur fréquence -

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

Méthode de recherche de solution

Il existe deux méthodes différentes pour trouver une solution, ce sont -

Méthode de la force brute

Dans cette méthode, nous bouclera, sélectionnera un élément particulier et déterminera son classement.

Exemple

#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;
}

Sortie

1.5 4 6 4 1.5 7 4

La complexité temporelle de ce programme est O(N*N), où N est la taille du tableau donné maintenant, comme vous pouvez le voir, notre complexité temporelle n'est pas bonne, donc ; nous améliorerons son efficacité pour mieux nous adapter à des contraintes plus élevées.

Méthode efficace

Dans cette méthode, nous allons prendre un nouveau tableau et le trier, puisque le tableau est trié, maintenant nous savons que tous les éléments avec le même rang seront ensemble, alors maintenant nous les faisons comme d'habitude Rank, et puis calculez le rang d’un élément spécifique.

Exemple

#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;
}

Sortie

1.5 3.5 6 3.5 1.5 7 5

Explication du code ci-dessus

Dans cette méthode, nous trions le tableau puis classons chaque élément depuis le début (le classement commence à partir de 1). Maintenant, si notre élément précédent est égal à l’élément actuel, nous incrémentons s et ajoutons à notre somme de classement. Lorsque notre élément change, nous séparons les rangs de l'élément précédent, actualisons les s et le total, et continuons avec notre code.

Conclusion

Dans cet article, nous avons résolu un problème pour trouver le classement de tous les éléments d'un tableau. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d’autres langages, tels que C, Java, Python et d’autres langages.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!