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 :

Tri par sélection


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Inscrit en
    Juin 2009
    Messages
    116
    Détails du profil
    Informations forums :
    Inscription : Juin 2009
    Messages : 116
    Points : 59
    Points
    59
    Par défaut Tri par sélection
    Bonjour tout le monde,
    Je débute dans l'algorithmique...j'ai compris le tri par sélection mais je n'ai pas compris pourquoi ces deux algorithmes fontionnent parfaitement bien sur Algobox :
    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
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
      VARIABLES
     i EST_DU_TYPE NOMBRE
     n EST_DU_TYPE NOMBRE
     tmp EST_DU_TYPE NOMBRE
     tab EST_DU_TYPE LISTE
     mi EST_DU_TYPE NOMBRE
     j EST_DU_TYPE NOMBRE
     DEBUT_ALGORITHME
     LIRE n
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       LIRE tab[i]
     FIN_POUR
     POUR i ALLANT_DE 0 A n-2
       DEBUT_POUR
       mi PREND_LA_VALEUR i
       POUR j ALLANT_DE i+1 A n-1
         DEBUT_POUR
         SI (tab[j]<tab[mi]) ALORS
           DEBUT_SI
           tmp PREND_LA_VALEUR tab[mi]
           tab[mi] PREND_LA_VALEUR tab[j]
           tab[j] PREND_LA_VALEUR tmp
         FIN_SI
       FIN_POUR
     FIN_POUR
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       AFFICHER tab[i]
     FIN_POUR
     FIN_ALGORITHME
    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
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
      VARIABLES
     i EST_DU_TYPE NOMBRE
     n EST_DU_TYPE NOMBRE
     tmp EST_DU_TYPE NOMBRE
     tab EST_DU_TYPE LISTE
     mi EST_DU_TYPE NOMBRE
     j EST_DU_TYPE NOMBRE
     DEBUT_ALGORITHME
     LIRE n
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       LIRE tab[i]
     FIN_POUR
     POUR i ALLANT_DE 0 A n-2
       DEBUT_POUR
       POUR j ALLANT_DE i+1 A n-1
         DEBUT_POUR
         SI (tab[j]<tab[i]) ALORS
           DEBUT_SI
           tmp PREND_LA_VALEUR tab[i]
           tab[i] PREND_LA_VALEUR tab[j]
           tab[j] PREND_LA_VALEUR tmp
         FIN_SI
       FIN_POUR
     FIN_POUR
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       AFFICHER tab[i]
     FIN_POUR
     FIN_ALGORITHME
    Ma question c'est pourquoi utiliser une variable mi pour stocker la valeur de i pour ensuite comparer tab[j] et tab[mi]...alors que le premier algo marche tout aussi bien...autrement dit qu'est-ce qui m'a échappé?
    Merci d'avance.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 033
    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 : 4 033
    Points : 9 331
    Points
    9 331
    Par défaut
    Si on prend ton algorithme, et qu'on ajoute une nouvelle variable k, et qu'on fait vers le milieu k = i* j, le nouvel algorithme continuera de fonctionner. La ligne ajoutée ne sert à rien. Dans ton cas, c'est pareil, A partir d'un algorithme qui fonctionne, on peut faire des modifications mineures, et l'algorithme continue de fonctionner.
    Mais l'algorithme perd en élégance et en lisibilité.

    L'objectif est bien évidemment d'avoir non seulement un algorithme qui donne le résultat voulu, mais aussi un algorithme élégant, sans instructions superflues.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre du Club
    Inscrit en
    Juin 2009
    Messages
    116
    Détails du profil
    Informations forums :
    Inscription : Juin 2009
    Messages : 116
    Points : 59
    Points
    59
    Par défaut
    Bonjour le forum
    Bonjour tbc92
    Merci pour la réponse
    Justement, je le pense aussi ...du coup je ne comprends pas pourquoi c'est le premier algorithme qui est repris dans tous les tutoriels et les cours que j'ai consultés sur le net....c'est pas normal. ..le deuxième algorithme (très simpliste ) c'est celui que j'ai fait pour donner la solution d'un exercice. ...y a quelque chose qui m'échappe forcément ! J'ai du faire une erreur.

  4. #4
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Salut,

    L'algorithme montré n'est pas celui du "tri par sélection", mais celui du "tri à bulles". Le tri par sélection c'est
    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
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    VARIABLES
     i EST_DU_TYPE NOMBRE
     n EST_DU_TYPE NOMBRE
     tmp EST_DU_TYPE NOMBRE
     tab EST_DU_TYPE LISTE
     mi EST_DU_TYPE NOMBRE
     j EST_DU_TYPE NOMBRE
     DEBUT_ALGORITHME
     LIRE n
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       LIRE tab[i]
     FIN_POUR
     POUR i ALLANT_DE 0 A n-2
       DEBUT_POUR
       mi PREND_LA_VALEUR i
       POUR j ALLANT_DE i+1 A n-1
         DEBUT_POUR
         SI (tab[j]<tab[mi]) ALORS
           DEBUT_SI
           mi PREND_LA_VALEUR j
         FIN_SI
       FIN_POUR
       SI (i!=mi) ALORS
           DEBUT_SI
           tmp PREND_LA_VALEUR tab[mi]
           tab[mi] PREND_LA_VALEUR tab[i]
           tab[i] PREND_LA_VALEUR tmp
       FIN_SI
     FIN_POUR
     POUR i ALLANT_DE 0 A n-1
       DEBUT_POUR
       AFFICHER tab[i]
     FIN_POUR
     FIN_ALGORITHME
    Et dans cet algorithme, l'utilisation de mi est indispensable.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  5. #5
    Membre du Club
    Inscrit en
    Juin 2009
    Messages
    116
    Détails du profil
    Informations forums :
    Inscription : Juin 2009
    Messages : 116
    Points : 59
    Points
    59
    Par défaut
    Bonjour le forum,
    Merci pour vos explications
    Bonne continuation à tous

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

Discussions similaires

  1. Réponses: 54
    Dernier message: 09/03/2013, 16h27
  2. [À télécharger] [Tri] Tri par sélection
    Par 3DArchi dans le forum Téléchargez
    Réponses: 0
    Dernier message: 06/11/2010, 20h45
  3. Tri par sélection du minimum récursif
    Par thechieuse dans le forum Pascal
    Réponses: 2
    Dernier message: 05/11/2008, 17h03
  4. problème tri par sélection
    Par scary dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 19/05/2008, 12h40
  5. Améliorer tri par sélection
    Par katrena99 dans le forum Pascal
    Réponses: 8
    Dernier message: 05/03/2007, 16h30

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