Discussion :

[elmcherqui]

bonjour , j'aurais deux question a propos de la stabilisation des algorithmes de tri.
<1ere question >
+ parmis 4 algorithmes de tri bien connus :
- tri par insertion .
- tri par fusion .
- tri par tas .
- tri rapide .
classez les par ordre de stabilité .

< 2eme question >
+ donner un shema simple qui rende stable n'importe quel algorithme de tri .Combien de temps et d'espace supplementaire votre shema demande t'il ?

| stable a mon avis c'est le nombre de deplacement de donnees ,ainsi que l'eloignement de chaque index par rapport a sa position finale qui augmentent la constante de la complexite |
| et non si il peux s'executer en O(n) dans le cas favorable et O(n^2) dans le plus defavorable , on ne parle pas de cette stabilite la |
-------------------------------------------------------

pour la premiere question par ordre croissant (du plus stable au moins stable ) je sais que sa depend des donnees mais on parle du cas moyen .
insertion > tri par tas > tri rapide > tri fusion

mon raisonnement :
le tri par insertion utilise juste des indice puis echange directement le nombre trouve avec sa position finale .
tri rapide : utilise deux indices aussi puis effectue des echanges minimes . le pivot est directement mis a sa place en fin de procedure .
tri par tas : la construction du tas est en ~=O(n) puis le tri opere avec des deplacement lg(n) maximum en plus d'un echange direct vers la position finale .
tri fusion : utilise un tableau en plus avec trop de copies de donnees et trop d'echanges et d'actualisations .

corrigez moi si j'ai faux ou si vous avez un autre point de vue .

/****************/

pour la seconde question j'arrive pas a la comprendre et je ne sais pas comment l'aborder parceque chaque algorithme a ses points forts et faible et donc avec chaque entree un algorithme de tri se comporte differement , je n'ai pas trouvé leur point commun .
le seul truc que je vois c'est arranger un peu les elements et donc le pré-trier
en utiliser un algo O(n) genre un tri-denombrement mais bon si un index est trop haut je suis mal .

y'a la methode de tri des pointeurs vu qu'ils pesent pas lourd , mais bon je crois pas que c'est le shema qu'ils veulent .

Merci de m'avoir lu , j'attend de vous lire a mon tour et d'avoir votre point de vue .
bonne soiree

[Jedai]

Tu ne pars pas dans la bonne direction... La stabilité est une caractéristique d'un algorithme de tri qui garde des éléments "égaux" selon sa fonction de comparaison dans le même ordre que dans le tableau initial. Par exemple supposons que tu ranges une liste de cartes par valeur, et que le tableau initial contienne "9 de carreau" et "9 de cœur" dans cet ordre, alors un tri stable te garantira que tu retrouvera ces éléments dans le même ordre dans le tableau trié, un tri instable pourrait parfaitement mettre le "9 de cœur" avant le "9 de carreau" dans le tableau trié.

Certains algorithmes sont "naturellement" stables, d'autres demandent certaines modifications pour le devenir, c'est pourquoi on te demande de les classer (même si personnellement je ne saurais ordonner le tri par fusion et le tri par insertion entre eux, ils sont tous deux naturellement stables).

Enfin, il est possible de rendre un tri stable avec une simple modification des données initiales, de la fonction de comparaison et un post-traitement sans jamais toucher à la procédure de tri elle-même, c'est-ce-qu'on te demande dans la seconde question.

--
Jedaï

[elmcherqui]

merci pour l'eclaircissement , je vais me repencher dans le probleme

[elmcherqui]

je donne mon cerveau au chat
si quelqu'un a une idee de comment faire ou des pistes je suis preneur .

[Jedai]

Tu comprends qu'on peut faire un tri multi-critère ? Par exemple, toujours dans mon jeu de carte, je peux trier prioritairement par couleur (dans l'ordre pique, cœur, carreau, trèfle par exemple) puis par valeur croissante (de sorte que le 4 de pique sera placé avant le 2 de carreau par exemple, mais le 2 de carreau avant le 3 de carreau). Le schéma qu'on te demande est un tri multi-critère, le premier "critère" étant l'ordre donné par la fonction de comparaison initiale et le second critère étant celui qui va t'assurer de la stabilité du tri, pour pouvoir utiliser ce second critère tout au long du tri il va falloir modifier les données initiales. A toi maintenant de trouver ce critère (après tout c'est tout de même un exercice, c'est mieux si tu trouves par toi-même et nous ne sommes pas un service d'aide au devoirs).

--
Jedaï

[elmcherqui]

A toi maintenant de trouver ce critère

mon raisonnement : si j'ai un tableau d'entier [1..n] par exemple , je cree un tableau double dimension de 2 lignes et n colonnes . la premiere lignes c'est le tableau initiale et la seconde je la remplie de 1 a n (ordre croissant) .
Cependant ce qui me gene , c'est que pour trier il faut quand meme rajouter un petit code dans la procedure de tri , dans le cas ou deux clés sont egales les trier par leur seconde clef qui se trouve dans la deuxieme ligne .

j'ai choisi tableau double dimension mais on peut tres bien utiliser un enregistrement , mais le probleme n'est pas la .

(après tout c'est tout de même un exercice, c'est mieux si tu trouves par toi-même et nous ne sommes pas un service d'aide au devoirs).
Jedaï

y'a pas de soucis a se faire de se coté la , je passe enormement de temps devant les exercices et ce n'est pas mes devoirs ce n'est meme pas dans notre programme d'etude , l'algorithmique est une passion pour moi .
sa me fait mal quand je vois ce genre de phrase qui m'ai destiné pourtant a lire mon premier post sa se voit que j'ai cherché .

[Jedai]

y'a pas de soucis a se faire de se coté la , je passe enormement de temps devant les exercices et ce n'est pas mes devoirs ce n'est meme pas dans notre programme d'etude , l'algorithmique est une passion pour moi .
sa me fait mal quand je vois ce genre de phrase qui m'ai destiné pourtant a lire mon premier post sa se voit que j'ai cherché .

Ben pas vraiment : après tout tu te trompais sur la signification de "stable" or une simple recherche de "tri stable" par exemple te donne une réponse comme celle-ci immédiatement.
Mais bon, si tu insistes qu'il ne s'agit pas de devoir et vu le temps écoulé...

mon raisonnement : si j'ai un tableau d'entier [1..n] par exemple , je cree un tableau double dimension de 2 lignes et n colonnes . la premiere lignes c'est le tableau initiale et la seconde je la remplie de 1 a n (ordre croissant) .
Cependant ce qui me gene , c'est que pour trier il faut quand meme rajouter un petit code dans la procedure de tri , dans le cas ou deux clés sont egales les trier par leur seconde clef qui se trouve dans la deuxieme ligne .

Un algorithme de tri normalement constitué ne contient pas la fonction de comparaison codée en dur, il ne serait pas utilisable de façon générale dans le cas contraire. Donc, en supposant que tu disposes d'une fonction de tri ainsi constituée :

Code :

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

sort :: (a -> a -> Ordering) -> [a] -> [a]

sort() prend une fonction de comparaison et une liste en paramètre et retourne la liste triée au moyen de la fonction de comparaison.

Tu veux donc créer un fonction stableSort ayant le même type :

Code :

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

stableSort :: (a -> a -> Ordering) -> [a] -> [a]

mais triant de façon stable.

Tu peux alors faire :

Code Haskell :

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

1
2
3
4
5
6
7
stableSort myCompare xs = map fst (sort newCompare newXs)
  where
    newCompare (x,n) (y,m) =
      case myCompare x y of
        EQ -> compare n m
        c  -> c
    newXs = zip xs [0..]

où newXs est donc une liste de paires (élément de xs, index dans xs) et newCompare commence par comparer les éléments avec la fonction de comparaison d'origine puis s'ils sont égaux compare leurs index d'origine.

Le "sort" originel est donc appelé avec ces nouveaux paramètres, note que son code n'a pas à être modifié. Puis "map fst" retransforme la liste de paires résultant du tri en une liste d'éléments de xs triés.

(NB : Un code Haskell idiomatique faisant cela serait plus proche de :

Code Haskell :

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

1
2
stableSort cmp = 
   map snd . sort ((cmp `on` snd) `mappend` (compare `on` fst)) . zip [0..]

mais je pense que l'autre version t'es plus compréhensible)

--
Jedaï

[elmcherqui]

Merci pour la reponse , j'ai vu ou tu veux en venir meme si j'ai rien compris au code haskell . c'est comme la fonction sort dans la bibliotheque stdlib en C . l'algorithme reste le meme juste la fonction de comparaison qui change .

Mais bon, si tu insistes qu'il ne s'agit pas de devoir et vu le temps écoulé...

c'est l'exercice 8.3.2 page 167 du bouquin introduction a l'algorithmique 2eme edition

[Jedai]

Merci pour la reponse , j'ai vu ou tu veux en venir meme si j'ai rien compris au code haskell . c'est comme la fonction sort dans la bibliotheque stdlib en C . l'algorithme reste le meme juste la fonction de comparaison qui change .

Tout à fait, avec un peu de pré-traitement et de post-traitement des données.

c'est l'exercice 8.3.2 page 167 du bouquin introduction a l'algorithmique 2eme edition

Excellent choix, ce livre est de qualité. Par contre je pense que le choix du C comme premier langage est une très mauvaise idée, enfin ce n'est pas rédhibitoire (après tout ce fut aussi mon parcours).

Bonne chance et bon courage pour la suite.
--
Jedaï

[elmcherqui]

Excellent choix, ce livre est de qualité. Par contre je pense que le choix du C comme premier langage est une très mauvaise idée, enfin ce n'est pas rédhibitoire (après tout ce fut aussi mon parcours).

en fait je programme en C puis je suis passé en C++ depuis bientot 2ans et demi . j'ai juste pas compris la question , quand ils disaient ne pas changer l'algo de tri je croyais ne pas y toucher du tous c'est pour cela sa m'a perturbé , en plus je suis deja passé par des exos de ce genre sur france ioi .

Bonne chance et bon courage pour la suite.

Merci beaucoup sa fait plaisir de lire des encouragement de gens plus experimenté que moi