Bonjour , viola je dois fair eun agenda et un des fonction et le tri multicriteres du carnet d'adresse :
 
j'ai un structure de type  

 
j'arrive maintenant a pouvoir faire pas mal de choses avec (remplir lieé ,enlever un maillon ect..).
Maheureusement un je ne voie pas comment fair eun trie multicriteres .
J'ai bien quelques idée (si un crite est egal au meme critere alors passer au critere suivant) mais  avec tout ces pointeurs je ne m'y retrouve plus .
Qulequ'un pourraitil m'aider a y voir plus clair merci d'avance

un tri multicritère ne diffère pas réellemet d'un tri sur un seul critère. La seule différence tiens au fait que la fonction de comparaison entre deux éléments (ici des contacts) devra savoir si le ième critère est utilisé pour la comparaison, et dans quel sens (a < b ou a > b ?)

le tri sur une liste chainée, tu peux oublier.

A mon avis le plus sûr et le plus simple c'est, quand tu veux trier ta liste chainée de N éléments :
1) Créer un tableau de N pointeurs vers les éléments de ta liste chainée
2) Faire un qsort() sur ce tableau
3) Parcourir le tableau ainsi trié pour rechainer ta liste dans le bon ordre

tu peux utiliser strcmp ou strncmp qui compare des chaine de caractere.
man strcmp
http://www.linux-france.org/articl [...] cmp-3.html
 
et puis au lieu de faire une fonctions de trie utilise plutot une fonctions qui insere au bon endroit dans une liste deja triee.

 
posterai plus tard, j'ai mon avis

Ha tiens, j'ai fini par retrouver mon drapal (l'avais oublié ce topic ).
En ce qui concerne le tri multicritère (sans parler de liste chainee), le meilleure tri pour ça est de faire un merge sort. Ce tri est garanti très stable ! c'est à dire que, par exemple, si tu tri un tableau de N entiers, les elements egaux ne sont pas échangés, ils restent dans le même ordre ! ex :
Cela ce montre en triant des structure de donnees, par exemple contenant une chaine de caractère et un chiffre :
Teste en triant d'abord sur les chaînes puis sur les chiffres, tu verras qu'une fois tes chiffres triés, tes chaînes sont échangées le moins possible (dans le cas ou des chiffres sont égaux dans ton tri).
 
Au passage tu remarqueras que la fonction sort de java sur des objets n'est pas le quick sort qui est utilisé mais le merge sort ! En effet le quick sort n'est pas du tout un tri stable...donc à eviter pour le tri multicritère.
Le tri multicritère peut être testé dans ton windows explorer en mettant l'affichage "détails", tri selon plusieurs critère (taille, type, nom, ...) et tu verras que si dans tes valeurs il y en a qui sont egales (par ex. des fichiers de meme type lorsque tu tri par type de fichiers) , les autres colonnes (nom fichier, taille,...) sont perturbées/échangées le moins possible voir pas du tout même...ce qui est interessant.

effectivement,
Le quicksort n'a de rapide que son nom.
Il est montré que sur des fichiers "presque" triés, le quicksort est bien moins performant qu'un merge sort.
Dans la pratique, la probabilité d'avoir un fichier "presque" triés est plus élevée que d'avoir un fichier totalement désordonné. C'est donc le tri fusion qui s'impose pour sa performance et au niveau de la gestion de l'espace mémoire pouvant être répartie.
 
edit :

 
External Sorting :
http://cis.stvincent.edu/carlsond/ [...] tsort.html

On dirait qu'un petit farceur a mélangé les touches de ton clavier...

 
Le quicksort est normalement le plus rapide, mais comme ça a été dit, il y a des cas ou il est en complexité O(n*n). Et il me semble que cela arrive quand la liste est triée exactement à l'envers, à vérifier ...
c'est quoi l'algorithme du tri du merge sort en Java ?  
Je me pose la question car en C++, la lib standard propose un stable_sort, qui est en O(n*log(n)*log(n)) soit log(n) fois plus qu'en Java.

 
Effectivement quand la liste est déjà triée, c'est en 0(n²). C'est pour cela qu'on peut utiliser des quicksort randomisé pour avoir plus de chance de se rapprocher de la complexité moyenne : 0(n log n)
 
Quicksort est un des algos de tri en 0(n log n) dans la catégorie de ceux qui trient par comparaison. Il existe des algos rapides qui trient en utilisant pas de comparaison...

Pour info, j'ai pas encore vu dans l'industrie de quick sort sur de fichiers de plusieurs centaines de megaoctets, et c'est en général sur ces fichiers où l'optimisation est très importante.
 
D'ailleurs dans ma précédente boite, on a payé une fortune un programme de tri fusion.
 
Le gros pb, c'est que le quick sort ne travaille qu'en mémoire vive...
Pour faire du External Sorting, les algos à base de merge sort sont très utilisés.

Uniquement pour la petite histoire du Quick Sort :
The Quicker Sort algorithm was first described by C.A.R.Hoare in the
Computer Journal, No. 5 (1962), pp.10..15, and in addition is frequently
described in computing literature, notably in D. Knuth's Sorting and
Searching.  The method used here includes a number of refinements :
The median-of-three technique described by Singleton (Communications
of the A.C.M., No 12 (1969) pp 185..187) is used, where the median
operation is also the special case sort for 3 elements.  This slightly
improves the average speed, especially when comparisons are slower
than exchanges, but more importantly it prevents worst-case behavior
on partly sorted files.  If a simplistic quicker-sort is run on a file
which is only slightly disordered (a common need in some applications)
then it is as slow as a bubble-sort.  The median technique prevents
this.
Another serious problem with the plain algorithm is that worst-case
behavior causes very deep recursion (almost one level per table
element !), so again it is best to use the median technique.
 
Donc depuis 1969, on a une amélioration de l'algo qui permet d'éviter le cas le pire où les éléments sont déjà triés. C'est un truc fendard avec l'algo d'origine : quand y'avait le moins de boulot à faire, c'est là où il ramait le plus !
En espérant que la lib de son compilo soit à jour, le QuickSort reste en moyenne d'ordre 0(n * log n).

 
+1 !
 
Ceux qui disent que le quicksort peut dans le pire des cas etre en O(n²), faudrait qu'il se mettent à jour. Depuis longtemps à été utlisé la technique de "median de 3", c'est à dire que, comme en general on prend le pivot soit le 1er element soit le dernier du tableau, ben pour pas prendre un pivot très mauvais (si le tableau est trie ou inversement trié) ben on prend la valeur median pour le pivot :
La valeur mediane se definit par :
Je prends la valeur a gauche du tableau, celle a droite et celle au milieu,...je repere la valeur mediane (c'est a dire celle entre les deux) et je l'echange avec la case que je prends comme pivot (soit la 1ere soit la derniere), a partir de la, mon pivot n'est plus tout pourrave comme dans le quicksort de base...sans parler que le quicksort peut etre accelere avec un tri insertion en fin de divsion du tableau (lorsque chaque sous tableau est d'une taille inf. ou egale a 7 en general).
 
NB: dans Java, ils utilisent le median de neuf valeur je crois meme.

Pour qu'il n'y ai pas de confusion dans les esprit, la fonction qsort() du C n'impose pas de méthode de tri. Seules les interfaces sont spécifiées, et seul le résultat compte. Chaque implémenteur de la bibliothèque standard fait ensuite ce qu'il veut...
 
Autrement dit, qsort() ne signifie pas obligatoirement algorithme Quick Sort.

C'est plus que vivement conseillé. Commencer à chercher un pivot sur base de trois valeurs pour un vecteur aussi petit et le trier avec QS, c'est pas très futé.
 
Dans la pratique, un QS "original" n'est pas non plus très réaliste, et je me demande qui l'utiliserait tel quel (et qui l'enseignerait tel quel aussi).
 
Tiens, c'est bien joli d'avoir étudié je ne sais plus combien de méthodes de tris, mais je me demande du coup s'il existe des techniques de prédictions qui permettent de choisir ou d'écarter a priori tel algo ou tel autre. P.e. on mesurerait sommairement le niveau de triage du vecteur, s'il est presque trié ou inversé, on peut écarter le QS, ...
 
Juste en passant.

Ca n'existe pas. Car il y a d'autres contraintes que le contenu des données qui pèsent sur le choix de l'algo de tri : taille des données à traiter, moyens de stockage, structure des données.
 
D'ailleurs, avec des listes chaînées, le tri fusion est un bon candidat. Il suffit de casser les liens puis de les reconstruire. Le problème du parcours de la liste ne se pose pas comme dans le QS où il n'est performant que sur les systèmes "direct" access memory

Disons pour un moyen de stockage et une structure de données... donnés. La taille des données ferait partie de la fonction d'évaluation.
 
Allez, prenons un vecteur de 1000 entiers à trier en mémoire sans contrainte. A l'oeil nu, tu peux voir si le vecteur est presque trié, est en ordre inverse ou est tout à fait mélangé. Cette évaluation est automatisable. De là, on peut déjà privilégier ou écarter certains algos.
 
Ensuite, on pourrait rajouter des critères (taille, contrainte mémoire, tri interne/externe).
 
Toujours pas ?

A vue d'oeil ca fait un parcours de liste pour un algo ...

Oui, et ?

Enfin je veux dire quand tu dis "à l'oeil nu " ca n'a pas vraiment de sens pour un algo.
 
Je sais bien que si tu fais un parcours de liste en 0(n) et que apres tu as un tri en 0(n log n) ca fait toujours 0(n log n) mais bon

En gros, ça veut dire que l'algo fait des statistiques sur un sous-ensemble de la liste avant de choisir l'algo (ou les algos) de tri approprié.

Ca doit pas être super couteux par rapport au tri lui-même, et le gain doit être substantiel.