Discussion :

[minhkhue]

Bonjour.
J'ai un problème que je voudrais demander pour avoir le meilleur tri avec une complexité acceptable.
J'ai un tableau au début

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int * tab = {5,3,6,2,4,7,4}

Ce tableau a la taille de 7. Je voudrais faire un tri sur ce tableau pour obtenir un tableau de résultat de sorte que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int *resultat = {5,2,0,4,6,1,3}

c'est à dire en fait d'ordonner les indices de tableau en fonctions de leur valeurs.

Ma proposition est que je vais créer une structure simple appelée Objet,par exemple,de 2 champs comprenant (int valeur, int indice). Donc le tableau tab devient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Objet * tab = {(5,0),(3,1),(6,2),(2,3),(4,4),(7,5),(4,6)}

Ensuite, je vais trier ce tableau tab en fonction des valeurs, avec un tri quick sort.
En fin, le tableau resultat est rempli en prenant les indices d'objets dans le tab trié.
Que pensez vous?
Avez vous une meilleure idée ?sans passer par une structure ?
Cordialement.

[cob59]

Boost.MultiIndex est conçu pour ce genre de problème, mais c'est vraiment l'artillerie lourde.
Si tu n'es pas à l'aise avec les templates il vaut mieux oublier.

[jblecanard]

Hello

Voila une technique qui fonctionne et qui est adaptable facilement à n'importe quelle structure de donnée que tu possèdes déjà. J'ai choisi d'utiliser des vectors car les tableaux C++ c'est le mal, mais libre à toi de faire comme il te chante. Note que tu n'as pas besoin d'un nouvelle struct ou de quoi que ce soit pour effectuer l'opération.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
 
void afficher(int iValue)
{
  std::cout << iValue << ",";
}
 
 
int main(int argc, char* argv[])
{
  // Données d'entrée
  std::vector<int> tab;
  tab.push_back(5);
  tab.push_back(3);
  tab.push_back(6);
  tab.push_back(2);
  tab.push_back(4);
  tab.push_back(7);
 
  // On insère dans un map car les clés d'un maps sont... triées !
  std::map<int,int> monTrieur;
  for(std::vector<int>::iterator it = tab.begin(); it != tab.end(); it++)
    monTrieur.insert(std::make_pair(*it,std::distance(tab.begin(),it)));
 
  // On met le résultat dans le tableau d'arrivée
  std::vector<int> resultat;
  for(std::map<int,int>::iterator it = monTrieur.begin(); it != monTrieur.end(); it++)
    resultat.push_back(it->second);
 
  // on affiche pour rigoler
  std::cout << std::endl;
  std::for_each(resultat.begin(), resultat.end(), afficher);
  std::cout << std::endl;
 
  return 0;
}

Je ne dis pas que c'est optimisé un max, mais ça fonctionne. N'hésite pas à poser des questions après avoir fait un tour dans la FAQ pour les parties que tu ne comprends pas.

[Lucien63]

J'ai trouvé le sujet intéréssant, alors j'ai tenté de le résoudre.

C'est du C.
Je sais que l'on est sur le forum C++ alors pas tapper.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
 
 
int main()
{
    int i, j;
 
    int tab[] = {5,3,6,2,4,7,4};
 
    int cpt[7] = {0};
 
    int resultat[7];
 
    for (i=1; i<7; i++)
      for (j=0; j<i; j++)
        tab[i]<=tab[j] ? cpt[i]++ : cpt[j]++;
 
    for (i=0; i<7; i++) resultat[cpt[i]]=i;
 
 
    // Affichage des tableaux :
 
    for (i=0; i<7; i++) printf("%d ",tab[i]);
    printf("\n");
    for (i=0; i<7; i++) printf("%d ",resultat[i]);
 
    return 0;
}

[minhkhue]

merci jblecanard et lucien63 pour votre aide ma solution marche très bien en testant, mais la solution de jblecanard me semble plus intéressant. A tester. Merci mille fois

[minhkhue]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

J'ai choisi d'utiliser des vectors car les tableaux C++ c'est le mal, mais libre à toi de faire comme il te chante.

Par contre, cette phrase m'intéresse le plus car inversement par rapport à mon encadrant qui aime les tableaux plus que les vector parce que pour elle, les tableaux sont tailles fixes et accédés plus vites que les vectors



C'est qui le gagnant?

[jblecanard]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

J'ai choisi d'utiliser des vectors car les tableaux C++ c'est le mal, mais libre à toi de faire comme il te chante.

Par contre, cette phrase m'intéresse le plus car inversement par rapport à mon encadrant qui aime les tableaux plus que les vector parce que pour elle, les tableaux sont tailles fixes et accédés plus vites que les vectors



C'est qui le gagnant?

C'est exact, les tableaux ont une taille fixe et l'accès est plus rapide, mais leur gestion est plus compliquée si de grands tableaux sont partagés par des objets ou des fonctions, car les problématiques de pointeurs et de gestion de la mémoire apparaissent. Le choix dépend de beaucoup d'informations dont je ne dispose pas. Note que dans le cas de petits tableaux comme dans ton exemple, ça ne va pas changer grand chose, à moins de faire le calcul des millions de fois.

Sinon, tu peux utiliser aussi Boost Array qui est justement fait pour être un tableau de taille fixe compatible STL. Tu récupères ainsi les avantages des deux dans ton cas ! Mais il faut boost, ou alors activer le support de C++11 dans ton compilateur s'il est assez récent pour cela.

[minhkhue]

merci jblecanard.
Je suis perdu pour la BoostArray, mais bon, je m'en occuppe pas ca pour l'instant...
Merci mille fois pour ton aide