IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

quel est le meilleur algo de tri de liste ?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Août 2004
    Messages
    94
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2004
    Messages : 94
    Points : 53
    Points
    53
    Par défaut quel est le meilleur algo de tri de liste ?
    bjr
    j'ai parcouru des sites sur le net pour trouver le meilleur algo de tri et je vais utiliser "Shell Sort" sur lequel ils indiquent le temps de parcourt =
    O(N(logN)2)
    quelqu'un peut m'expliquer cette formule (surtout le "O") (et c'est pour une liste de 30000 par exemple)
    et est-que c'est le meilleur algo de tri pour la rapidité de calcul et pour des listes d'une moyenne de 30000 et pouvant aller à des millions de lignes au maximum (mais c'est rare donc vaut mieux priviligier un algo qui aurait plus de perf sur des listes d'une moyenne de 30000)?
    merci d'avance.

  2. #2
    Membre expérimenté Avatar de BainE
    Inscrit en
    Mai 2004
    Messages
    1 327
    Détails du profil
    Informations forums :
    Inscription : Mai 2004
    Messages : 1 327
    Points : 1 544
    Points
    1 544
    Par défaut
    bonjour, si je me souvient bien le O ne veu pas dire grand chose, c'est la norme la complexité du tri s'exprime en O de ...
    la c'est un tri qui augmente lorgarithmiquement par rapport au nombre d'element de ton tableau, le log peut etre plus ou moins fort selon le coef associé...

    Pour ton tri de chaine, je dirai un tridichotomique qui si je me rapelle bien est tres performant pour les listes a taille consequente

    Bon courage
    "vaste programme"

  3. #3
    Membre régulier Avatar de hamster
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    137
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2003
    Messages : 137
    Points : 123
    Points
    123
    Par défaut
    ça n'a pas sa place ici, il fallait poster dans la partie Algorithmes

    La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.

    Il n'existe pas de tri le plus efficace au sens strict.
    Certains tris sont plus performants à partir d'une taille donnée.

    Le tri par bulle, le tri par insertion et le tri par sélection sont en O(n²)
    ça signifie que pour une liste de 30000 éléments, dans le pire des cas, il faudra 900'000'000 opérations.

    Il existe des tris plus évolués, tels que Quick Sort, Merge Sort, Heap Sort, qui sont en O(n log (n)).
    Pour 30000 éléments il faudra donc environ 1'630'000 opérations

    Enfin des tris en O(n) existent, mais necessitent l'utilisation d'une deuxieme liste de taille égale à celle qu'on veut trier

    http://fr.wikipedia.org/wiki/Tri

  4. #4
    Membre à l'essai
    Profil pro
    Inscrit en
    Février 2003
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 11
    Points : 12
    Points
    12
    Par défaut
    Citation Envoyé par hamster
    La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.
    Avant tout, les notations O(f) et o(f) sont des notations mathématiques introduites par Landau.

    O(f) signifiant de l'ordre de grandeur de la fonction f
    o(f) signifiant négligeable devant la fonction f.

    Cordialement
    Loran

  5. #5
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Attention, toutefois : le tri de liste et le tri de tableau ne fonctionnement pas DU TOUT de la même manière !!
    Typiquement, même sur une liste doublement chaînée, le QuickSort est totalement inefficace car le temps de parcours "carbonise" le gain de l'algorithme... :-(

    Pour une liste, l'insertion d'un élément ne coûte pas "cher" en performances, alors que dans un tableau, c'est le pire des cas.
    Inversement, accéder à n'importe quel élément d'un tableau ne coûte pas plus "cher" qu'il soit en début ou fin, alors que sur une liste...

    La problématique est exactement la même que pour le tri de fichiers "séquentiels" : je crois me rappeler que le tri par fusion était le plus performant à ce petit jeu.

    Dans ton cas, surtout si tu sais que ta liste n'est pas triée, tu peux optimiser la séparation de ta liste en deux en prenant un élément sur deux (au lieu de prendre les N/2 premiers)...

    Si tu te débrouilles bien, tu ne dois avoir besoin de ne modifier QUE le chaînage de ta liste pendant le tri, et tu ne devrais quasiment pas consommer de mémoire en dehors de celle utilisée par la récursivité.

    Une page que j'apprécie particulièrement :
    http://www.dailly.info/algorithmes-de-tri/index.php
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juillet 2005
    Messages : 55
    Points : 61
    Points
    61
    Par défaut
    Pour en revenir a la notation O:

    - O(n) est une majoration, cela signifie que dans le pire des cas, l'algorithme aura une complexité n (comme l'a dit hamster)
    - θ(n) est la complexité exacte de l'algorithme
    - Ω(n) est une minoration, c'est a dire que l'algorithme aura au moins une complexité en n.

  7. #7
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    En fait pour être clair, O devrait théoriquement être la notation de Landau et g(n)=O(f(n)) signifier exactement :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    pour tout N entier, il existe A réel strictement positif tel que pour tout n >= N, g&#40;n&#41; <= A*f&#40;n&#41;
    Mais en réalité les notations varient selon les livres et les auteurs... Donc O() peut parfois désigner une équivalence, parfois une borne supérieure, etc.

    Le shell sort est complexe à mettre en place, et n'est pas le plus performant, donc...

    Comme l'a rappelé Mac LAK, les tableaux et les listes chainées ne se trie pas de la même façon : shématiquement le tri le plus utilisé pour les tableaux est le quicksort (tri rapide) et le tri le plus utilisé pour les listes est le merge sort (tri par fusion). Tous deux ont des performances moyennes en O(n*log(n) ) mais le tri fusion est plus "stable" que le quicksort car celui-ci peut atteindre du O(n^2) dans le pire des cas (si la liste est déjà presque triée) tandis que le tri fusion reste en O(n*log(n)).

    Les tri en O(n) sont limités à des cas particuliers, par exemple le tri par tas, qui demande un tableau auxiliaire de la taille de l'ensemble des données possibles à trier (par exemple si tu tries sur l'ensemble des entiers naturels inférieur à 1000, tu auras besoin d'un tableau auxiliaire de longueur 1000, quelle que soit la taille du tableau à trier).

    --
    Jedaï

  8. #8
    Membre régulier
    Homme Profil pro
    Retraité
    Inscrit en
    Mars 2004
    Messages
    137
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Mars 2004
    Messages : 137
    Points : 116
    Points
    116
    Par défaut
    Citation Envoyé par hamster
    La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.
    Le tri par bulle, le tri par insertion et le tri par sélection sont en O(n²)
    ça signifie que pour une liste de 30000 éléments, dans le pire des cas, il faudra 900'000'000 opérations.

    Il existe des tris plus évolués, tels que Quick Sort, Merge Sort, Heap Sort, qui sont en O(n log (n)).
    Pour 30000 éléments il faudra donc environ 1'630'000 opérations
    Je ne suis pas spécialiste de la complexité.

    Mais, bon, j'aimerais bien mettre mon grain de sel quand même.
    Si un algorithme A demande n² opérations pour s'effectuer et un autre 1000000 n², on dira que l'un et l'autre sont en O(n²). Par conséquent, l'expression "tel algorithme est en O(n²)" ne donne pas une idée du nombre d'opérations à utiliser. Elle indique simplement, si N désigne le nombre d'opérations à effectuer, que lorsque n tend vers l'infini, le rapport N/n tend vers une constante C qui peut être gigantesque ou très petite.

    C'est la raison pour laquelle :
    Citation Envoyé par hamster
    Il n'existe pas de tri le plus efficace au sens strict.
    Certains tris sont plus performants à partir d'une taille donnée.
    Le tri à bulles n'a pas de concurrent pour n=3. Par contre il est archi nul dès que n augmente (100,1000,10000) précisément parce qu'il est en O(n²), alors que le Quicksort voit son temps de calcul augmenter presque proportionnellement à n - en général -.

    En outre, cela n'indique pas le "pire des cas". Cela peut caractériser le comportement "moyen", ou le comportement "le meilleur" ou le comportement "le pire" d'un algorithme selon les données qui lui sont fournies. On dira par exemple que le Quicksort est en O(nlog(n)) "en général", mais qu'il est en O(n²) dans le pire des cas (exceptionnel).

    Cela dit, il est bien possible que le Quicksort demande effectivement n*log(n) opérations ; simplement l'expression "le Quicksort est en O(nlog(n))" ne le dit pas ; elle dit simplement que le nombre d'opérations du Quicksort est C*n*log(n) sans préciser la valeur de C.
    Si un algorithme est en O(nlog(n)) le nombre d'opérations sera C1*n*log(n). Si un autre algorithme est en n² le nombre d'opérations sera C2*n².
    Il est clair qu'on trouvera toujours une valeur de n assez grande pour que le premier aille plus vite que le deuxième. Toute la question repose sur les valeurs relatives de C1 et C2. A priori, même si C1 et C2 sont assez différents, quand n=30000, n²=900 000 000 et nlog(n) environ 300000. Même sans connaître C1 et C2 on peut bien supposer que pour n=30000 il n'y aura pas photo, c'est le premier qui gagnera.

Discussions similaires

  1. Quel est le meilleur livre sur le SQL ?
    Par Marc Lussac dans le forum Livres
    Réponses: 78
    Dernier message: 03/10/2019, 21h04
  2. Quel est le meilleur script PHP de portail (CMS) ?
    Par Lana.Bauer dans le forum EDI, CMS, Outils, Scripts et API
    Réponses: 187
    Dernier message: 18/10/2012, 08h45
  3. quel est le meilleur algo pour table de routage
    Par boboss123 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 09/05/2012, 18h36
  4. Réponses: 87
    Dernier message: 06/07/2011, 16h33
  5. Quel est le meilleur Routeur-adsl ???
    Par loki dans le forum Développement
    Réponses: 4
    Dernier message: 12/11/2002, 19h05

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo