Trier avec doublons

[Valentin03]

Bonjour bonjour, je viens faire la mendicité d'un algo de tri de 500 valeurs comportant des doublons; le tri à bulle de base ne marche pas et sur le net, je ne trouve rien qui va bien
Je ne suis pas étudiant, ce n'est pas un TP, et j'ai les neurones qui fument.
Du pseudo code ou du basic ferait l'affaire ou du lien
A vot' bon coeur et merci d'avance.

[Ben314]

Salut,
Je ne suis pas totalement certain de comprendre le terme de "doublons".
A priori, j'aurais bien dit que cela signifiait que le tableau contenant éventuellement plusieurs fois la même valeur, sauf que dans ce cas, l'algorithme de tri à bulle marche parfaitement bien :

Code: Tout sélectionner

// Tri à Bulle : Entrée = N , Tableau[1..N]
Fini=Faux
Tant que non(Fini)
 |Fini=Vrai
 |Pour i de 1 à N-1 faire
 | |Si Tableau[i]<Tableau[i+1] alors
 | | |Echanger(Tableau[i],Tableau[i+1]); Fini=Faux;


[Valentin03]

Merci Ben, je vais essayer ton truc mais je doute,
Il y a effectivement plusieurs fois les mêmes valeurs, que je veux conserver, car le tableau de valeurs est couplé à un tableau de chaînes (traité en parallèle, non représenté ici)
J'ai fais avec ça:

Code: Tout sélectionner

for i = 1  to  n-1
    for j = 1  to  n-i
        if bubble(j) > bubble(j-1) then
            temp = bubble(j)
            bubble(j) = bubble(j+1)
            bubble(j+1) = temp
        end if
    next j
next i


Et ça ne trie pas; d'après moi, il faut extraire les petits en double et les mettre par paquets dans un autre tableau, Mais je ne vois pas trop comment faire

[Valentin03]

ça y est, j'en ai trouvé un qui marche
Je le mets là pour si quelqu'un en a besoin

Code: Tout sélectionner

FOR i=1 TO n
    FOR j=1 TO (n-1)
        IF bubble(j) > bubble(j+1) THEN
            temp=bubble(j)
            bubble(j)=bubble(j+1)
            bubble(j+1)=temp
        END IF
    NEXT j
NEXT i


[Ben314]

Sans vouloir être méchant avec toi, c'est totalement exactement la même chose que ce que j'ai mis ci dessus, sauf que ça continue à tourner même si le truc est trié au bout de quelques "passes" de la bulle.

Et concernant le fait que ton premier algo ne marche pas, ça n'a absolument rien à voir avec la notion de doublon, mais plutôt avec le fait que l'algo en question, si tu regarde ce qu'il fait, ben y'a pas une seule fois où il compare l'élément bubble[n] avec un autre. Et de l'autre coté, ton algo compare régulièrement bubble[0] avec des trucs.

Enfin bref, c'est un algo qui doit fonctionner pour trier un tableau bubble[0..N-1] (style convention du langage C ou d'autre langages) et faut pas s'étonner que ça fasse des truc on ne peut plus louche si ton tableau de départ, c'est du bubble[1..N] (ton deuxième algo, lui ce qu'il trie, c'est bien du bubble[1..N])

Et je terminerais en te signalant que c'est la seule (et unique) différence entre les deux algo. que tu as tapé (donc rien à voir avec des problèmes d'homonymie...)

[Rockleader]

Coucou =)

Et je vais me permettre d'ajouter un peu ma sauce à tout ça n'ayant pas réellement compris la demande; voyant Trier un tableau avec doublon (je me suis dis que tu voulais supprimer les doublons car aucune différence entre trier un tableau avec ou sans doublon), mais après j'ai vu qu'il te fallais conserver les doublons.


Deux choses, je ne sais pas en quel langage tu codes, mais il existe certaines structures dans des langages comme Java qui permettent automatiquement de supprimer les doublons à l'insertion.

Ce sont les Set et c'est vraiment très pratique, ça peut s'implémenter bien sûr dans d'autres langages.

Code: Tout sélectionner

Set<String> set =  new HashSet<String>() ;

 // ajout d'élément
System.out.println("J'ajoute un : " + set.add("un")) ;
System.out.println("J'ajoute deux : " + set.add("deux")) ;

 // ajout d'un doublon : échec
System.out.println("J'ajoute encore un : " + set.add("un")) ;

Ce genre de structure marche très bien si tu veux supprimer tes doublons.



Maintenant si tu veux garder les doublons comme j'ai cru le comprendre; alors de mon point de vue, il serait plus intéressant de faire ta propre structure, de façon à ne pas garder 10 fois le chiffre 2 par exemple, mais seulement de garder en mémoire que 2 doit être présent 10 fois.


Sa se fait très facilement avec une classe en poo ou une structure dans un langage comme C cf en bas

Code: Tout sélectionner

typedef struct Element_frequence{

int elem;
int frequence=0;

}

Par la suite tu fais simplement un tableau d'élément fréquence au lieu d'entier.
De cette façon tu n'auras pas de doublon, mais tu conserveras la fréquence, et tu auras des tableaux plus légers.

On pourrait même aller jusqu'à faire une autre structure qu'un tableau, un arbre de recherche binaire serait bien plus adapté ici à mon avis.


Si je me permets justement d'évoquer ces deux points c'est parce que tu dis que tu n'es pas étudiant, et donc je ne vois pas l'intérêt de faire un tableau stockant des doublons en dur si ce n'est pas pour un exo...

[fatal_error]

@rockleader

tu peux vouloir manipuler des doublons...
considères le tableau
var tasks = [
{valeur: 1, taskId:2},
{valeur: 1, taskId:3},
{valeur: 2, taskId:4}
]
maintenant, imagine que tu as un ordonnanceur qui choisit __la__ tache la plus importante à défoncer...
il faut pas considérer la clé d'unicité comme valeur, mais comme valeur/task

sauf qu'évidemment, tu peux choisir de trier par valeur...

[Valentin03]

Coucou =)je ne vois pas l'intérêt de faire un tableau stockant des doublons en dur si ce n'est pas pour un exo...

Pour tout dire il s'agit de 4 tableaux de valeurs couplés à un tableau de chaînes:
(Nom aliment; val protide, val lipide, val glucide, val Kcalories)
Si les doublons de valeur peuvent êtres identiques, il se réfèrent chacun à autre chose de différent (nom de l'aliment et autres valeurs associées)
Ce qui les rend différents tout en étant semblables
Comme le dit plus savamment fatal-error