Problème de tri

Version imprimable

13/07/2011, 14h21
minhkhue

Problème de tri

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:

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:

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:

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.
:mouarf::mouarf::mouarf:
13/07/2011, 15h24
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.

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:

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.

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:

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

19/07/2011, 13h24
minhkhue

merci jblecanard et lucien63 pour votre aide :aie: ma solution marche très bien en testant, mais la solution de jblecanard me semble plus intéressant. A tester. Merci mille fois:ccool::ccool:
19/07/2011, 13h27
minhkhue

Code:

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

:mouarf::mouarf::mouarf:

C'est qui le gagnant?
19/07/2011, 13h40
jblecanard

Citation:

Envoyé par minhkhue

Code:

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

:mouarf::mouarf::mouarf:

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.
19/07/2011, 13h54
minhkhue

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