1. #1
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut Dénombrer les méthodes de tri

    Salut à tous.

    Combien existe-t-il de méthodes de tri actuellement ?

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  2. #2
    Modérateur
    Avatar de gangsoleil
    Profil pro
    R&D en systemes informatiques bas niveau Unix/Linux
    Inscrit en
    mai 2004
    Messages
    9 251
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : R&D en systemes informatiques bas niveau Unix/Linux

    Informations forums :
    Inscription : mai 2004
    Messages : 9 251
    Points : 26 407
    Points
    26 407

    Par défaut

    42
    Modérateur "C", "Informatique Générale & Hardware" et "Unix"
    Les règles du forum

  3. #3
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    La question n'était pas que fait 6x9, mais bien la liste des méthodes de tri connue à ce jour.
    En voici un extrait :
    --> tri par insertion
    --> tri à bulle
    --> tri par sélection
    --> tri rapide
    --> tri fusion
    --> tri arborescent
    --> tri par partition
    --> tri par shell

    Ce que je recherche, c'est le nom de tris connus à ce jour, ainsi que leur algorithme.

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  4. #4
    Modérateur
    Avatar de gangsoleil
    Profil pro
    R&D en systemes informatiques bas niveau Unix/Linux
    Inscrit en
    mai 2004
    Messages
    9 251
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : R&D en systemes informatiques bas niveau Unix/Linux

    Informations forums :
    Inscription : mai 2004
    Messages : 9 251
    Points : 26 407
    Points
    26 407

    Par défaut

    Il en existe énormément, mais tous les algorithmes ne sont pas applicables(*) à tous les cas. Notamment, il y a des algorithmes qui seront très performants sur des matrices creuses, mais très mauvais sur des matrices pleines, d'autres prévus pour les ordinateurs quantiques, d'autres qui seront plus orientés vers des gros volumes de donnés, etc...

    (*) : bien sur, tu peux toujours appliquer un algo à un cas pour lequel il n'est pas adapté, mais les performances peuvent être désastreuses. Par exemple, quick-sort est mauvais sur les données déjà triées (ca tend vers O(n^3) si mes souvenirs sont bons), et ce n'est pas pour rien que dans certains cas tu vois une répartition random du tableau avant de faire un tri, pour être presque certain de ne pas tomber dans le cas O(n^3).
    Modérateur "C", "Informatique Générale & Hardware" et "Unix"
    Les règles du forum

  5. #5
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Je ne cherche pas à appliquer une quelconque méthode de tri, mais juste à faire le recensement de ce qui existe déjà.
    Entre autre, la complexité de l'algorithme, les performances, l'originalité de l'approche, de quoi elle dérive, la taille mémoire nécessaire ...
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  6. #6
    Modérateur
    Avatar de gangsoleil
    Profil pro
    R&D en systemes informatiques bas niveau Unix/Linux
    Inscrit en
    mai 2004
    Messages
    9 251
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : R&D en systemes informatiques bas niveau Unix/Linux

    Informations forums :
    Inscription : mai 2004
    Messages : 9 251
    Points : 26 407
    Points
    26 407

    Par défaut

    Tu as quelques éléments de réponse sur wikipedia fr : https://fr.wikipedia.org/wiki/Algorithme_de_tri
    Et plus sur wikipedia en anglais : https://en.wikipedia.org/wiki/Sortin...ing_algorithms

    Que tu manque-t-il ? Une liste exhaustive est impossible à établir, il y en a trop
    Modérateur "C", "Informatique Générale & Hardware" et "Unix"
    Les règles du forum

  7. #7
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Salut gangsoleil.

    Et où peut-on trouver les algorithmes qui sont associés à ces tris ?

    Quel est l'algorithme de tri le plus rapide ?

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  8. #8
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Doctorant
    Inscrit en
    août 2008
    Messages
    22 087
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Doctorant
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 087
    Points : 117 791
    Points
    117 791

    Par défaut

    Citation Envoyé par Artemus24 Voir le message
    Et où peut-on trouver les algorithmes qui sont associés à ces tris ?


    Citation Envoyé par Artemus24 Voir le message
    Quel est l'algorithme de tri le plus rapide ?
    Dans quel cas ? Certains fonctionnent mieux quand les données sont presque triées, d'autres quand elles sont dans l'ordre inverse, etc. Le tri rapide est, en moyenne, l'un des algorithmes les plus rapides, mais sans certitude (complexité en O(n log n) en moyenne, O(n^2) dans le pire cas) ; le tri par tas est asymptotiquement idéal, avec une complexité de O(n log n) dans le pire cas, mais en pratique n'est pas toujours le plus rapide.

    Sans oublier que toute combinaison d'algorithmes de tri peut faire un nouvel algorithme de tri plus rapide (par exemple, un tri par fusion, appliqué récursivement jusqu'à une certaine taille de blocs à fusionner, où un autre algorithme est utilisé), comme https://en.wikipedia.org/wiki/Timsort.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  9. #9
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 598
    Points
    2 598

    Par défaut

    Bonjour,
    il y a deux grandes catégories de tri de tableau (par extension de liste même si c'est un poil différent) :
    • les tris par comparaisons entre éléments (la majorité des tris «classiques» que l'on apprend)
    • les tris sans comparaisons entre éléments (radix sort, bucket sort, bogo sor, spaghetti sortt)


    Il est important de commencer à faire cette différence car sinon les complexité temporelle ne signifieront rien. Dans le premier cas, les complexités temporelles sont donnée en nombre de comparaisons/échanges entre éléments ; dans le second cas elles sont simplement données en terme d'opérations élémentaires. C'est pourquoi on ne se trompe pas en disant que les algo de la première catégorie ne pourront jamais faire mieux que O(n lg n) (comparaisons/échanges sous-entendu) tout en disant que radixsort est un tri en O(n) (même si là on sous entend aussi que les nombres traités ne sont pas arbitrairement grands, une constante cachée étant l'ordre de grandeur du plus grand élément).

    Maintenant il faut aussi se dire qu'il n'existe pas un algorithme universel de tri qui battrait tous les autres tout le temps. Pour chaque algorithme et pour chaque implémentation on pourra toujours trouver une entrée pour laquelle une autre implémentation d'un autre algorithme sera «meilleure» pour autant que tu donnes un sens à «meilleur».
    Il existe aussi des algorithme de tri qu'on ne reconnaît pas en tant que tel. Par exemple si tu n'as que 3 éléments à placer en ordre tu ne vas pas faire un quicksort, tu vas simplement faire quelques if et le tour est joué. Un autre exemple est la recherche d'un chemin hamiltonien qui peut être associé à un algorithme de tri car on crée de facto un ordre.

    C'est un sujet très vaste.

  10. #10
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Salut à tous.

    Citation Envoyé par picodev
    C'est un sujet très vaste.
    C'est justement pour ça que je pose la question.
    Non pas que je sois totalement ignare en ce domaine, mais plutôt pour faire une mise à niveau de mes connaissances.

    Il y a des tris que je n'ai jamais entendu parlé. Par exemple, les tris :
    --> spaghetti
    --> idiot
    --> shaker
    --> peigne
    --> de batcher
    --> cocktail
    --> tim sort
    --> par tas
    --> intro sort
    --> smooth sort

    Il est fort possible que je les connaisse sous un autre nom ! Mais difficile de se faire une opinion sans avoir l'algorithme.
    De plus, n'avons-nous pas dans ces tentatives multiples, des exercices de style qui n'ont d'intérêt que de laisser le nom de leut auteur à la postérité.

    Citation Envoyé par dourouc05
    Citation Envoyé par Artemus24
    et où peut-on trouver les algorithmes qui sont associés à ces tris ?
    La question n'est pas si idiote que cela car on ne trouve pas toujours ce que l'on cherche, même avec google.
    Je prends au hasard le tri spaghetti. Bien que je connaisse la programmation spaghetti, je suppose que cela n'a aucun rapport ni avec les spaghettis, et encore moins avec l'usage abusif que l'on faisait du "goto" dans les langages dits non structurés.

    Ce qui m'intéresse, ce sont les tris internes, c'est-à-dire un tableau mémoire qui va nous servir à effectuer par la suite des rechercher.
    Prenons l'exemple d'une tableau totalement vide au départ. J'insère les éléments étape par étape.
    Quel est la meilleure façon de procéder ?
    1) de faire le tri du tableau quand celui-ci sera totalement rempli ?
    2) de faire le tri à chaque nouvelle insertion dans le tableau ?

    Autre approche. Puisque je dois faire une recherche dans un tableau, est-il encore nécessaire de faire un tri ?
    Je pense aux tables associatives, c'est-à-dire sur l'adressage calculée.
    Qu'en pensez-vous ?

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  11. #11
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    2 024
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 2 024
    Points : 4 426
    Points
    4 426

    Par défaut

    Des fois, il ne faut pas chercher à comprendre

    Le problème du tri par tas (Heapsort), c'est qu'il nécessite beaucoup de déplacements et en majorité, entre des cases éloignées successibles de provoquer des "cache misses" (par exemple, on déplace toujours la racine (la première valeur) vers la fin)

    Donc, Edsger Dijkstra a créé le tri Smoothsort pour palier ces inconvénients: Smoothsort Demystified, basé non pas sur un tas mais sur "Leonardo Trees" (<- prends de l'aspirine, ça tape fort )

  12. #12
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 252
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 252
    Points : 2 642
    Points
    2 642

    Par défaut

    - J'imagine que dans tes recherches, tu es tombé sur ce lien : https://en.wikipedia.org/wiki/Spaghetti_sort, où on liste une 40aine de méthodes de tris.

    - Pour préparer des données et optimiser les recherches dans ces données, l'idéal n'est pas de trier les données, mais de créer un index. Regarde du côté de l'index B-tree.

    - 42, ce n'est pas égal à 6x9, mais à 6x7 .

  13. #13
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Doctorant
    Inscrit en
    août 2008
    Messages
    22 087
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Doctorant
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 087
    Points : 117 791
    Points
    117 791

    Par défaut

    Citation Envoyé par tbc92 Voir le message
    - 42, ce n'est pas égal à 6x9, mais à 6x7 .
    Inculte .
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  14. #14
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 252
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 252
    Points : 2 642
    Points
    2 642

    Par défaut

    Citation Envoyé par dourouc05 Voir le message
    Là, je reconnais que j'avais raté un épisode !

  15. #15
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Salut à tous.

    Citation Envoyé par foetus
    Des fois, il ne faut pas chercher à comprendre
    Et pourquoi donc ?

    @ foetus : le tri smoothsort ressemble beaucoup au tri arborescent. En quoi est-il meilleur que le tri arborescent ?
    Par contre, je ne comprends pas bien ce qui caractérise le tri par tas vis-à-vis du tri arborescent.

    @ tbc92 : oui, en effet, j'ai trouvé ce lien où il est question du tri spaghetti.
    Mais j'ai plutôt préféré cet autre lien : http://www.pourlascience.fr/ewb_page...ttis-18987.php
    D'après ce que j'ai compris, cela consiste à rechercher le nombre le plus grand, à l'extraire de la liste et à recommencer l'opération sur la liste des non classé.
    En quoi, cette méthode de tri est plus pertinente ?

    Citation Envoyé par tbc92
    - 42, ce n'est pas égal à 6x9, mais à 6x7 .
    Si vous faites cette remarque, c'est que vous ne connaissez rien à "La grande question sur la vie, l'univers et le reste".
    C'est tiré de l'oeuvre de "Douglas Adams Le Guide du voyageur galactique".
    A la réponse "42" de gangsoleil, j'ai répondu "6x9" en faisant un clin d'oeil à l'ouvre de Douglas Adams.

    Personne n'a répondu à mes des questions :
    Citation Envoyé par Artemus24
    Ce qui m'intéresse, ce sont les tris internes, c'est-à-dire un tableau mémoire qui va nous servir à effectuer par la suite des rechercher.
    Prenons l'exemple d'une tableau totalement vide au départ. J'insère les éléments étape par étape.
    Quel est la meilleure façon de procéder ?
    1) de faire le tri du tableau quand celui-ci sera totalement rempli ?
    2) de faire le tri à chaque nouvelle insertion dans le tableau ?

    Autre approche. Puisque je dois faire une recherche dans un tableau, est-il encore nécessaire de faire un tri ?
    Je pense aux tables associatives, c'est-à-dire sur l'adressage calculée.
    Qu'en pensez-vous ?
    Il est fort possible que la réponse se trouve dans la remarque de tbc92 :
    Citation Envoyé par tbc92
    Pour préparer des données et optimiser les recherches dans ces données, l'idéal n'est pas de trier les données, mais de créer un index.
    Mais je ne comprends pas trop bien ce que vous entendez par "index" ? Ce terme est-il en relation avec les bases de données ?
    Si c'est le cas, l'index est un fichier à part, qui contient un pointeur vers la page de la table où est stockée la valeur maximale de cette clef.
    Comme vous devez vous en douter, cet index est trié sur la clef, pas toutes les clefs car on stocke que la plus grande clef de la page où elle se trouve.
    Si vous recherchez une clef et que cette clef est plus petite que celle de l'index, alors si elle existe, elle doit obligatoirement se trouver dans la page, pointé par l'adresse.

    Quand je parle de l'adressage calculée (hash coding ), il s'agit de trouver une adresse à partir d'une clef disons alphabétique.
    Il s'agit de fonction de hachage. Et l'on nomme cela des tables associatives.

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  16. #16
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    2 024
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 2 024
    Points : 4 426
    Points
    4 426

    Par défaut

    Citation Envoyé par Artemus24 Voir le message
    Et pourquoi donc ?

    @ foetus : le tri smoothsort ressemble beaucoup au tri arborescent. En quoi est-il meilleur que le tri arborescent ?
    Par contre, je ne comprends pas bien ce qui caractérise le tri par tas vis-à-vis du tri arborescent.
    Si le tri Smoothsort n'est pas célèbre c'est parce qu'il hyper difficile à comprendre, malgré un code court.

    Et si tu te poses des questions, c'est que tu n'as rien compris sur la différence entre un tas, "Leonardo Trees" et un simple arbre biniaire

  17. #17
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Salut foetus.

    Citation Envoyé par Foetus
    Et si tu te poses des questions, c'est que tu n'as rien compris sur la différence entre un tas, "Leonardo Trees" et un simple arbre binaire
    Pire que cela, je ne me suis jamais vraiment penché sur toutes les différences qui existe dans ces tris.
    Comme beaucoup d'informaticiens, j'utilise quelques algorithmes que j'ai appris et rencontré dans mes différentes missions quand je travaillais. (oui, je suis à la retraite).

    Citation Envoyé par foetus Voir le message
    Si le tri Smoothsort n'est pas célèbre c'est parce qu'il hyper difficile à comprendre, malgré un code court.
    Si vous me le dites, c'est que je ne suis pas le seul à ne pas comprendre l'intérêt de ce tri.

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  18. #18
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 598
    Points
    2 598

    Par défaut

    Citation Envoyé par Artemus24 Voir le message

    Personne n'a répondu à mes des questions :
    Citation Envoyé par Artemus24 Voir le message
    Ce qui m'intéresse, ce sont les tris internes, c'est-à-dire un tableau mémoire qui va nous servir à effectuer par la suite des rechercher.
    Prenons l'exemple d'une tableau totalement vide au départ. J'insère les éléments étape par étape.
    Quel est la meilleure façon de procéder ?
    1) de faire le tri du tableau quand celui-ci sera totalement rempli ?
    2) de faire le tri à chaque nouvelle insertion dans le tableau ?

    Autre approche. Puisque je dois faire une recherche dans un tableau, est-il encore nécessaire de faire un tri ?
    Je pense aux tables associatives, c'est-à-dire sur l'adressage calculée.
    Qu'en pensez-vous ?
    @+
    Il faut faire la différence entre la structure de donnée + les algos et une implémentation spécifique.

    Ce qu'on attend d'une hashtable est une complexité temporelle moyenne et/ou amortie constante O(1) et en O(n) dans le pire des cas pour les opérations de recherche, d'insertion et de délétion, n étant le nombre d'éléments que contient la table, la complexité temporelle étant en opérations élémentaires.
    À la limite on ne demande pas plus. Si ton implémentation respecte ce cahier des charges alors tu es assuré de toutes les propriétés des hashtable.

    Ensuite il y a les détails d'implémentation pour un langage particulier et parfois pour une plateforme particulière, voire pour des données particulières.
    Si tu as une bonne fonction de hachage, avec peu de collisions alors la question ne se pose pas. Ta fonction de hachage te donne un id auquel tu accède en temps constant puis tu cherches dans une liste la clé demandée. Comme le taux de collision est faible que tu fasses une recherche binaire dans une liste que tu maintiens triée ou que tu tries avant la recherche c'est dérisoire … autant faire une recherche brute. Les performances ne se dégraderont que lorsque les collisions seront nombreuses.
    Mais attention le fait de maintenir une liste triée a un coup de l'ordre de O(k log k) où k est le nombre moyen de collisions. Si tu tombes dans un cas dégénéré où k n'est plus négligeable face à n alors tu n'auras plus une hashtable car tex complexités temporelles s'effondreront, mais bon c'est le risque de maintenir une structure triée.

    L'idée est vraiment de maintenir un taux de collision bas pour s'éviter justement d'avoir à maintenir un ordre.

  19. #19
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    2 024
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 2 024
    Points : 4 426
    Points
    4 426

    Par défaut

    Citation Envoyé par Artemus24 Voir le message
    Si vous me le dites, c'est que je ne suis pas le seul à ne pas comprendre l'intérêt de ce tri.
    Si, il y a un intérêt c'est une amélioration du tri par tas "Heapsort"

    (je le redis en différent) Lorsqu'on construit un tas on va parcourir le tableau de gauche à droite. Mais on va faire des inversions de valeurs qui ne sont pas contiguës et donc peuvent entrainer des "cache misses".
    Par comparaison, le tri rapide "Quicksort", et moins sujet aux "cache misses", parce qu'on compare successivement les valeurs.
    Et ensuite, le tas construit, rebelote: on va ranger la racine (la première valeur) vers la fin.

    Donc le tri "Smoothsort", va utiliser des "Leonardo Trees", parce que (c'est dit dans mon lien), c'est comme un tas mais à l'envers: en gros les feuilles sont plus à gauche et les racines plus à droite, donc plus dans un ordre chronologique

  20. #20
    Expert éminent Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    2 687
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 2 687
    Points : 8 159
    Points
    8 159

    Par défaut

    Salut à tous.

    J'ai commencé par les tris les plus simples. Voici mon source écrit en 'C' :
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    360
    361
    362
    363
    364
    365
    366
    367
    368
    369
    #include <stdlib.h>
    #include <stdio.h>
     
    /*********************/
    /*                   */
    /*     Affichage     */
    /*                   */
    /*********************/
     
    void Afficher(const int *ptr, const int z, const int n)
    {
    	int i;
     
    	switch (z)
    	{
    		case 1:
    				printf("Avant : ");
    				break;
     
    		case 2:
    				printf("Après : ");
    				break;
    	}
     
    	for (i=0; i<n; i++)
    		printf("%d ", *(ptr+i));
     
    	printf("\n");
     
    	if (z == 2)	printf("\n");
    }
     
    /********************/
    /*                  */
    /*     Echanger     */
    /*                  */
    /********************/
     
    void Echanger(int v[], const int i, const int j)
    {
    	int temp;
     
    	temp = v[i];
    	v[i] = v[j];
    	v[j] = temp;
    }
     
    /***********************/
    /*                     */
    /*     Tri à Bulle     */
    /*                     */
    /***********************/
     
    void TriBulle(int v[], int n)
    {
    int flag;
     
    	do {
    		flag = 0;
     
    		for (int i=0; i<n; i++)
    		{
    			if (v[i] > v[i+1])
    			{
    				Echanger(v, i, i+1);
    				flag = 1;
    			}
    		}
    	n--;
    	} while (flag);
    }
     
    /******************************************/
    /*                                        */
    /*     Tri Shaker (ou bidirectionnel)     */
    /*                                        */
    /******************************************/
     
    void TriShaker(int v[], const int n)
    {
    	int flag=1, iMin=0, iMax=n;
     
    	while (flag)
    	{
    		flag=0;
     
    		for (int i=iMin; i < iMax; i++)
    		{
    			if (v[i] > v[i+1])
    			{
    				Echanger(v, i, i+1);
    				flag = 1;
    			}
    		}
    		iMax--;
     
    		for (int i=iMax-1; i >= iMin; i--)
    		{
    			if (v[i] > v[i+1])
    			{
    				Echanger(v, i, i+1);
    				flag = 1;
    			}
    		}
    		iMin++;
    	}
    }
     
    /**********************/
    /*                    */
    /*     Tri Peigne     */
    /*                    */
    /**********************/
     
    void TriPeigne(int v[], const int n)
    {
    	int flag, iPas=n;
     
    	do {
    		flag=0;
    		iPas /= 1.3;
    		if (iPas < 1) iPas = 1;
     
    		for (int i=0; i<=(n-iPas); i++)
    		{
    			if (v[i] > v[i+iPas])
    			{
    				Echanger(v, i, i+iPas);
    				flag = 1;
    			}
    		}
    	} while (flag || iPas>1);
    }
     
    /*****************************/
    /*                           */
    /*     Tri par Sélection     */
    /*                           */
    /*****************************/
     
    void TriSelection(int v[], const int n)
    {
    	for (int i=0; i<=n; i++)
    	{
    		int iMin = v[i];
    		int iPos = i;
     
    		for (int j=i+1; j<=n; j++)
    			if (iMin > v[j])
    			{
    				iMin = v[j];
    				iPos = j;
    			}
     
    		Echanger(v, i, iPos);
    	}
    }
     
    /*****************************/
    /*                           */
    /*     Tri par Insertion     */
    /*                           */
    /*****************************/
     
    void TriInsertion(int v[], const int n)
    {
    	int j;
     
    	for (int i=1; i<=n; i++)
    	{
    		int elem = v[i];
     
    		for (j=i; j>0 && v[j-1]>elem; j--)
    			v[j] = v[j-1];
     
    		v[j] = elem;
    	}
    }
     
    /*********************/
    /*                   */
    /*     Tri Gnome     */
    /*                   */
    /*********************/
     
    void TriGnome(int v[], const int n)
    {
    	int i=1;
     
    	while (i <= n)
    	{
    		if (v[i-1] <= v[i])	{ i++; }
    		else				{ Echanger(v, i-1 , i);
    							  if (i > 1) i--; }
    	}
    }
     
    /*********************/
    /*                   */
    /*     Tri Shell     */
    /*                   */
    /*********************/
     
    void TriShell(int v[], const int n)
    {
    	for (int iEcart=n/2; iEcart>0; iEcart/=2)
    	{
    		for (int i=iEcart; i<=n; i++)
    		{
    			for (int j=i-iEcart; j>=0 && v[j]>v[j+iEcart]; j-=iEcart)
    				Echanger(v, j , j+iEcart);
    		}
    	}
    }
     
    /**********************************/
    /*                                */
    /*     Tri Rapide (quicksort)     */
    /*                                */
    /**********************************/
     
    void TriRapide(int v[], const int iGauche, const int iDroite)
    {
    	int i, iPivot;
     
    	if (iGauche >= iDroite)
    		return;
     
    	Echanger(v, iGauche, (iGauche+iDroite)/2);
     
    	iPivot = iGauche;
     
    	for (i=iGauche+1; i<=iDroite; i++)
    		if (v[i]<v[iGauche])
    			Echanger(v, ++iPivot, i);
     
    	 Echanger(v, iGauche,  iPivot);
     
    	TriRapide(v, iGauche,  iPivot-1);
    	TriRapide(v, iPivot+1, iDroite);
    }
     
    /**********************/
    /*                    */
    /*     Tri Fusion     */
    /*                    */
    /**********************/
     
    void Fusion (int v[], const int iDeb, const int iMed, const int iFin)
    {
    	int t[20];
     
    	for (int i=iDeb, j=iMed+1, k=0; k<=(iFin-iDeb); k++)	{
    		if (  i  > iMed)	{ t[k] = v[j++]; }	else		{
    		if (  j  > iFin)	{ t[k] = v[i++]; }	else		{
    		if (v[i] < v[j])	{ t[k] = v[i++]; }
    		else				{ t[k] = v[j++]; }	}}}
     
    	for (int k=0; k<=(iFin-iDeb); k++)		{ v[k+iDeb] = t[k]; }
    }
     
    /* ------------------------------------------------------------------------ */
     
    void TriFusion(int v[], const int iDeb, const int iFin)
    {
    	if (iDeb == iFin)	return;
     
    	int iMed = (iDeb + iFin) / 2;
    	TriFusion(v, iDeb,   iMed);
    	TriFusion(v, iMed+1, iFin);
    	   Fusion(v, iDeb,   iMed, iFin);
    }
     
    /********************************/
    /*                              */
    /*     Procédure Principale     */
    /*                              */
    /********************************/
     
    int main(void)
    {
    	int iTab01[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab02[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab03[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab04[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab05[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab06[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab07[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab08[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
    	int iTab09[20] = {5,8,3,4,6,9,7,2,5,7,3,6,5,9,2,7,6,2,3,1};
     
    	printf("+---------------------+\n");
    	printf("|     Tri à Bulle     |\n");
    	printf("+---------------------+\n\n");
     
    	Afficher(iTab01, 1, 20);
    	TriBulle(iTab01, 19);
    	Afficher(iTab01, 2, 20);
     
    	printf("+--------------------+\n");
    	printf("|     Tri Shaker     |\n");
    	printf("+--------------------+\n\n");
     
    	Afficher(iTab02, 1, 20);
    	TriShaker(iTab02, 19);
    	Afficher(iTab02, 2, 20);
     
    	printf("+--------------------+\n");
    	printf("|     Tri Peigne     |\n");
    	printf("+--------------------+\n\n");
     
    	Afficher(iTab03, 1, 20);
    	TriPeigne(iTab03, 19);
    	Afficher(iTab03, 2, 20);
     
    	printf("+---------------------------+\n");
    	printf("|     Tri par Sélection     |\n");
    	printf("+---------------------------+\n\n");
     
    	Afficher(iTab04, 1, 20);
    	TriSelection(iTab04, 19);
    	Afficher(iTab04, 2, 20);
     
    	printf("+---------------------------+\n");
    	printf("|     Tri par Insertion     |\n");
    	printf("+---------------------------+\n\n");
     
    	Afficher(iTab05, 1, 20);
    	TriInsertion(iTab05, 19);
    	Afficher(iTab05, 2, 20);
     
    	printf("+-------------------+\n");
    	printf("|     Tri Gnome     |\n");
    	printf("+-------------------+\n\n");
     
    	Afficher(iTab06, 1, 20);
    	TriGnome(iTab06, 19);
    	Afficher(iTab06, 2, 20);
     
    	printf("+-------------------+\n");
    	printf("|     Tri Shell     |\n");
    	printf("+-------------------+\n\n");
     
    	Afficher(iTab07, 1, 20);
    	TriShell(iTab07, 19);
    	Afficher(iTab07, 2, 20);
     
    	printf("+--------------------+\n");
    	printf("|     Tri Rapide     |\n");
    	printf("+--------------------+\n\n");
     
    	Afficher(iTab08, 1, 20);
    	TriRapide(iTab08, 0, 19);
    	Afficher(iTab08, 2, 20);
     
    	printf("+--------------------+\n");
    	printf("|     Tri Fusion     |\n");
    	printf("+--------------------+\n\n");
     
    	Afficher(iTab09, 1, 20);
    	TriFusion(iTab09, 0, 19);
    	Afficher(iTab09, 2, 20);
     
    	/*===========================*/
    	/*     Fin du Traitement     */
    	/*===========================*/
     
    	return 0;
    }
    Bien sûr, chaque tri donne le même résultat. J'aurai dû tester la performance, mais bon, ce n'est pas exactement ce que je cherche à faire.
    Pour l'instant, mes tris préférés sont ceux en récursivité.

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 1
    Dernier message: 29/03/2017, 11h44
  2. Réponses: 0
    Dernier message: 30/09/2009, 18h13
  3. Réponses: 0
    Dernier message: 30/09/2009, 18h13
  4. Meilleure méthode de tri pour les combobox
    Par boss_gama dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 12/03/2009, 10h48

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