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

 

  1. #1
    Membre du Club Avatar de Redgard
    Homme Profil pro
    x
    Inscrit en
    décembre 2014
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : x

    Informations forums :
    Inscription : décembre 2014
    Messages : 90
    Points : 60
    Points
    60

    Par défaut Trier un tableau de nombre

    Bonjour,

    Je me suis amusé à créer une fonction de trie de tableau de nombres, commençant par la première case du tableau, puis la comparant à toutes les autres cases, avant de passer à la suivante. Ce qui donne ça:
    Code : 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
    void SortTab(int tab[], int sizeTab) {
    	int numTemp;
     
    	for (int i = 0; i < sizeTab - 1; i++)
    	{
    		for (int j = i + 1; j < sizeTab; j++)
    		{
    			if (tab[i]>tab[j])
    			{
    				numTemp = tab[i];
    				tab[i] = tab[j];
    				tab[j] = numTemp;
    			}
    		}
    	}
    }
    Mais lors de mes périgrinations sur les internets, je suis tombé sur cette asertion:
    Il existe de très nombreuses méthodes de tri, dont:
    • Chercher le plus petit élément du tableau, l'échanger avec le premier, recommencer en partant du second élément
    • Trier le tableau à partir de la gauche, en intercalant les élément un à un dans la partie triée
    • Comparer les éléments adjacents et les échanger s'ils sont dans le mauvais ordre, recommencer sur tout le tableau jusqu'à ce que tous les éléments adjacents soient dans le bon ordre
    • Prendre la valeur d'un élément au hasard, mettre à gauche les éléments plus petit et à droite les plus grands, recommencer sur les parties droite et gauche jusqu'à ce qu'elles n'aient plus qu'un élément

    La dernière méthode est beaucoup plus efficace que les trois premières.
    Si je vois plus ou moins comment faire les 3 premiers tris, j'ai un peu plus de mal à visualiser comment coder la dernière. Est-ce que quelqu'un n'aurait pas un exemple?


    Merci d'avance,
    Red'

  2. #2
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    2 509
    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 509
    Points : 5 735
    Points
    5 735

    Par défaut

    Citation Envoyé par Redgard Voir le message
    Est-ce que quelqu'un n'aurait pas un exemple?
    Tri rapide - Quicksort (<- lien wiki français)

    Le tien s'appelle tri à bulles (<- lien wiki français)

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 411
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 411
    Points : 17 924
    Points
    17 924
    Billets dans le blog
    1

    Par défaut

    Bonjour

    Autant voir concrètement ce qui se passe.

    Ici
    des différentes méthode de tri avec des danseurs. Ils virevoltent et se comparent en claquant des talons puis ils se placent conformément à l'algorithme. Amusant.

    Sinon plus professionnel


    A noter: le qsort est une des meilleures méthodes de tri sauf dans un cas précis: si le tableau est déjà trié mais à l'envers. Dans ce cas, le remettre à l'endroit prendra plus de temps que la plus pourrie des autres méthodes de tri.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Membre du Club Avatar de Redgard
    Homme Profil pro
    x
    Inscrit en
    décembre 2014
    Messages
    90
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : x

    Informations forums :
    Inscription : décembre 2014
    Messages : 90
    Points : 60
    Points
    60

    Par défaut

    Merci pour les liens.

    J'ai commencé à regarder ce qu'il en était mais débutant sur ce sujet, les vidéos me semblent encore assez abstraites.

    J'ai commencé des fonctions à ce sujet: https://code.sololearn.com/csI1CfOLkI9L/#c

    Désolé pour le temps de latence, mais je montre pas mal de signe de fatigue donc je dois faire avec.

  5. #5
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 411
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 411
    Points : 17 924
    Points
    17 924
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Redgard Voir le message
    J'ai commencé à regarder ce qu'il en était mais débutant sur ce sujet, les vidéos me semblent encore assez abstraites.
    Ben pour la première (le qsort dansant) le premier danseur de gauche est pris comme pivot. Puis il scrute chacun des autres et dès qu'un danseur est plus petit que lui, il échange sa place avec ledit danseur. Quand tout le tableau est passé, le pivot est alors à sa place définitive. Là il se retourne car il ne bougera plus.

    Puis chacun des groupes gauche et droite se sépare et ensuite l'algorithme est repris pour chacun des deux sous-groupes. Et etc etc etc jusqu'à ce que les sous-groupes soient de 1 élément. Au final tout le tableau est trié. C'est le tri-pivot appelé aussi "tri rapide" parce que (généralement) excellemment rapide.
    En fait, sa rapidité (si on doit le comparer par exemple à ce que tu as écrit et qui est le tri à bulles) est due au fait que dans chaque sous-groupe, les comparaisons ne concernent que le sous-groupe considéré. Dans ton tri (tri à bulles), chaque élément est en permanence comparé à tous les autres alors que dans le qsort, chaque élément ne sera comparé qu'avec les éléments de son sous-groupe et ignorera les éléments des autres sous-groupes.

    A noter toutefois une erreur dans la chorégraphie. A la minute 3.05, quand le sous-groupe de gauche a terminé et que c'est le sous-groupe de droite qui commence l'algo, le pivot (qui est donc le premier de son sous-groupe) devrait danser avec le second du sous-groupe (puisque la comparaison commence du premier et monte ensuite élément par élément). Or il danse avec le dernier de son groupe. Ca ne change rien au résultat mais ce n'est pas une répétition exacte de l'algorithme initial comme ça aurait du.

    Pour la seconde vidéo c'est en effet moins évident. On arrive toutefois à reconnaitre le qsort ou le merge-sort mais faut évidemment connaitre le principe de ces tris.
    A noter le bogo-sort (que je ne connaissais pas et que je ne comprenais pas sur la vidéo) et qui m'a éclaté quand je suis allé voir son principe
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

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

Discussions similaires

  1. Trier un tableau par nombre d'occurences d'un mot
    Par mitch08 dans le forum Langage
    Réponses: 11
    Dernier message: 22/06/2016, 18h59
  2. Réponses: 2
    Dernier message: 26/02/2014, 13h30
  3. Réponses: 8
    Dernier message: 14/11/2007, 10h27
  4. Trier un tableau par ordre croissant
    Par Halleck dans le forum Algorithmes et structures de données
    Réponses: 15
    Dernier message: 01/11/2004, 00h04
  5. trier un tableau et compter des elements du tableau
    Par remi51 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 17/06/2002, 16h51

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