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

Discussion: Tri par insertion

  1. #1
    Futur Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    mai 2013
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Santé

    Informations forums :
    Inscription : mai 2013
    Messages : 11
    Points : 8
    Points
    8

    Par défaut Tri par insertion

    Bonjour
    Ça fait un mois que je galère avec les algos de tri, à chaque fois je relis le code je pense que je comprends mais je me trompe toujours
    Je sais qu'il y a un problème avec mon raisonnement mais je finis par être fatiguée je n'arrive plus à réfléchir
    Merci beaucoup d'avance


    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
    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
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
     
    void randomise (int * array, int grandeur)
    {
    	for (int i = 0 ; i < grandeur ; i++)
    		array[i] = rand() % 51 ;
     
    }
     
     
    void affiche (int * array, int grandeur)
    {
    	for (int j = 0 ; j < grandeur ; j++)
    		printf("%4d", array[j]);
    	printf("\n");
    }
     
     
    int main ()
     
    {
    	srand(time(NULL)) ;
     
    	int * tableau;
     
    	int taille ;
    	printf("quelle est la taille du tableau ? \n");
    	scanf("%d", &taille) ;
     
    	tableau = malloc (taille * sizeof(int)) ;
     
    	randomise (tableau, taille) ;
     
    	printf("avant tri \n");
    	affiche (tableau, taille) ;
     
    	//je vais parcourir tout le tableau moins  une valeur
    	//à l'intérieur : je compare toutes les valeurs
    	for (int i = 0 ; i < taille ; i++)
    		for (int j = 1 ; j < (taille-1) ; j ++)
    			if (tableau[j] < tableau[j-1])
    			//permutation
    			{
    				//int valeur = tableau[j-1] ;
    				int temp = tableau[j];
    				for (j-1 ; tableau[j-1] < tableau[j] ; j--)
    					tableau[j+1] = tableau[j];
    				tableau[j] = temp ;
    			}
     
     
    	printf("apres tri \n");
    	affiche (tableau, taille) ;
     
    	free(tableau) ;
     
    	return 0 ;
    }

  2. #2
    Membre du Club Avatar de ekieki
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    avril 2014
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 60
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : avril 2014
    Messages : 23
    Points : 44
    Points
    44

    Par défaut

    1) Tu parles d'erreur dans ton raisonnement. Tout ce qu'on voit, c'est du code.
    Si tu veux qu'on t'aide à trouver les erreurs dans ton raisonnement, explique-le (*), en détail et avec précision.

    2) Ligne 48, que veux-tu faire avec ton for ?

    3) ce tri devrait être dans une fonction, au lieu de trainer au milieu du main

    -----
    (*) il est probable qu'en cherchant à l'expliquer, tu trouveras ce qui ne va pas. Mais il faut chercher.

    Y a qu'à faire comme si on était des canards en plastique : https://fr.wikipedia.org/wiki/M%C3%A...d_en_plastique

  3. #3
    Expert confirmé
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    845
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 845
    Points : 4 379
    Points
    4 379

    Par défaut

    Pour le tri par insertion, il n'y a que 2 boucles :
    - la première est basée sur le fait que les n premiers éléments sont triés (on peut donc commencer à l'indice 1 car s'il y a un élément il est forcément trié.)
    - la seconde consiste à prendre l'élément qui juste après la liste triée. On la parcourt vers l'arrière pour rechercher où insérer cet élément.

  4. #4
    Futur Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    mai 2013
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Santé

    Informations forums :
    Inscription : mai 2013
    Messages : 11
    Points : 8
    Points
    8

    Par défaut

    En fait j'a regardé des tutos expliquant le principe du tri par insertion mais je dois probablement griller les étapes
    Je n'ai pas l'habitude de décomposer suffisamment mon raisonnement, il est possible que ça vienne de ça
    Je fais une formation accélérée et je bute un peu avec l'algo, on nous a donné un gros travail perso et je me suis cassé les dents dessus tant pis
    Après coup mon message fait vraiment gros boulet
    Ma formation va trop vite par rapport à mes capacités mais c'est un autre débat
    Du coup je fais les exos sur le site de france IOI et je vais tenter la méthode du canard dès que je bute sur quelque chose
    Merci à vous deux

  5. #5
    Membre du Club Avatar de ekieki
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    avril 2014
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 60
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : avril 2014
    Messages : 23
    Points : 44
    Points
    44

    Par défaut

    Citation Envoyé par eowyn113 Voir le message
    En fait j'a regardé des tutos expliquant le principe du tri par insertion mais je dois probablement griller les étapes
    Je n'ai pas l'habitude de décomposer suffisamment mon raisonnement, il est possible que ça vienne de ça
    C'est même certain. Le problème des débutants c'est que les premiers essais qu'ils font (des programmes triviaux genre hello world) les conduisent à sous-estimer largement le degré de rigueur dont ils auront besoin pour programmer (il faut TOUT détailler). Et comme de l'autre côté ils surestiment leurs capacités cognitives, ça coince vite.

    Quelques exemples :

    - pas la peine de découper en fonctions, ça va comme ça
    - ok mes variables ont des noms absurdes, mais je m'y retrouve
    - la présentation de mon code est crado, mais je verrai après
    - les commentaires, je les mettrai quand ça marchera
    - hje suis sur que ça marche, pourquoi vérifier ?
    - si_ça marche pas, je vais essayer de changer des trucs


    Ben non, quand ça part comme ça, ça ne marchera qu'au prix d'une grosse galère, et encore pas sur.

    Faut penser qu'un programme, c'est pas juste un truc qui marche ou pas, c'est un TEXTE sur lequel on va TRAVAILLER, souvent pendant des heures. Donc, bien nommer les choses pour ne pas consacrer des neurones à des conneries, comme se rappeler que ligne 72 la variable z désigne la taille du tableau. Faut l'appeler "taille", merde, quoi. Parce que 4 ou 5 variables comme ça, et c'est foutu, on perd une énergie monstrueuse à se souvenir, au lieu de travailler sur la signification du code. Et si on demande de l'aide à quelqu'un, il va se barrer en courant en voyant le travail de sagouin.

Discussions similaires

  1. besoin d'aide pour le tri par insertion.
    Par argon dans le forum Algorithmes et structures de données
    Réponses: 19
    Dernier message: 18/05/2006, 12h15
  2. tri par insertion et Structures
    Par bonjour69 dans le forum C
    Réponses: 2
    Dernier message: 23/12/2005, 13h46
  3. [LG] Le tri par insertion d'un enregistrement
    Par phoebee dans le forum Langage
    Réponses: 4
    Dernier message: 01/09/2005, 21h38
  4. [LG]Tri par insertion dans une liste chainée
    Par mister_dsg dans le forum Langage
    Réponses: 4
    Dernier message: 18/12/2003, 23h34

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