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é .