+ Répondre à la discussion
Affichage des résultats 1 à 3 sur 3
  1. #1
    Invité de passage
    Femme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 6
    Points : 3
    Points
    3

    Par défaut Tri Quickstart : tri rapide

    Bonjour à tous !

    J'essaye d'effectuer en langage C, un tri Quicksort : Tri Rapide

    Au départ j'ai 8 chiffres : 5,3,9,1,8,6,4,7

    Le pivot est determiné de façon : prend le premier élément du groupe à trier

    Donc ici le pivot sera 5

    Tout ce qui est inférieur à 5 je veux l'insérer dans un nouveau tableau, et de même pour tout ce qui est supérieur à 5

    Ce qui donne un tableau t1 avec 3,1,4 (donc 3 sera le pivot) et un tableau t2 avec 9,8,6,7 (donc le pivot sera 9)

    Et ainsi de suite ..

    Jusqu'a ce qu'il y'est que un seul chiffre dans un tableau ou plus aucun dans ce cas la on s'arrête.

    J'ai commencé à écrire le code mais je suis bloquée concernant le pivot quand il est égal à 5, je n'arrive pas à créer les deux tableaux t1 et t2

    Code :
    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
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream.h>
     
    int main()
    {
        int n,p,i,j,u,t[7],t1[2],t2[3];
        j=-1;
        i=1;
        u=-1;
        t[0]=5;
        t[1]=3;
        t[2]=9;
        t[3]=1;
        t[4]=8;
        t[5]=6;
        t[6]=4;
        t[7]=7;
     
          for(i=0;i<8;i++)
                        {
                            printf("\t%d",t[i]);
                        }
     
     
        p=t[0];
     
        printf("\nLe pivot est %d\n",p);
     
     
        if(p>t[i])
        {
                     i=i+1;
                     j=j+1;
                     t1[j]=t[i];
                     printf("%d",t[j]);
        }
        else
        {
         i=i+1;
         u=u+1;
         t2[u]=t[i];
         printf("\t%d",t[u]);
        }
     
     
    getchar();
    getchar();
    getchar();
    }
    Pouvez vous m'aider et me dire ou sa ne va pas ?
    Merci à vous

    PS: Je suis une débutante qui vient juste de débuter le langage C (c'est mon premier langage , je suis actuellement en 1ère année de BTS Informatique)

  2. #2
    Expert Confirmé Sénior
    Avatar de Sve@r
    Homme Profil pro Frédéric
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    4 680
    Détails du profil
    Informations personnelles :
    Nom : Homme Frédéric
    Âge : 46
    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 : 4 680
    Points : 10 596
    Points
    10 596

    Par défaut

    Bonjour
    Ca ne va pas à plusieurs niveaux
    • Tout d'abord, tu veux remplir t1 et t2 avec des nombres issus de t donc l'étape de base sera de parcourir chaque élément de t (donc une boucle) et si t[x] est inférieur à p tu le copies dans t1[y] et tu incrémentes y et si t[x] est supérieur à p tu le copies dans t2[z] et tu incrémentes z. Là, tu compares juste t[i] (que vaut i à cet endroit ?) avec p. Qu'en est-il des autres t[x] ???
    • Ensuite tu dis "et ainsi de suite" ce qui signifie qu'il faut recommencer le même algorithme avec t1 et t2 (qui seront eux-mêmes dispatchés dans t11 et t12 pour t1 et t21 et t22 pour t2). Et si t11 a plus d'un élément il faut encore recommencer et, là vraiment, ainsi de suite. Et qu'en sera-t-il si on veut trier non pas un tableau de 8 éléments mais de 500 ???


    Donc ce genre de mécanisme est tout à fait possible en C mais il implique de connaitre la notion de récursivité. Cette notion part du principe qu'une fonction se déroule dans un espace local et isolé avec ses propres variables. Il lui est donc tout à fait possible d'appeler un clone d'elle-même et attendre le retour de ce clone. Ledit clone effectuant ses propres calculs avec sa propre zone de travail elle-aussi isolée et si besoin, pouvant lui-aussi appeler un autre clone de lui-même et attendre son résultat.
    Une fois que le clone le plus bas se termine, il renvoie son résultat à son appelant qui peut donc terminer son travail et renvoyer le résultat à son propre appelant et, là encore, ainsi de suite.
    Exemple de récursivité: la factorielle
    Code c :
    1
    2
    3
    4
    5
    unsigned long fact(unsigned short n)
    {
        if (n < 2) return 1;
        return n * fact(n - 1);
    }
    Donc fact(5) cherchera à calculer 5 * fact(4) et attendra le retour de fact(4) pour finir. Mais fact(4) cherchera à calculer 4 * fact(3) qui, lui, cherchera 3 * fact(2) qui cherchera 2 * fact(1).
    fact(1) étant prévu par le test (qu'on appelle "test de fin de récursivité") renvoie 1 donc fact(2) calcule 2 * 1 et renvoie 2 à fact(3) qui calcule 3 * 2 et renvoie 6 à fact(4) qui calcule 4 * 6 et renvoie 24 à fact(5) qui calcule 5 * 24 et renvoie au final 120 à l'appelant initial.

    Donc avec un tel exemple c'est une notion pas compliquée à percevoir mais il faut la connaitre avant d'essayer de l'appliquer sur un algorithme plus complexe...

    PS: un tableau peut se remplir à la déclaration en écrivant: int t[]={5,3,9,1,8,6,4,7}.
    PS2: la récursivité est un faux ami car s'il simplifie l'écriture de résolution en profondeur, il est super gourmand pour le système (qui doit, quand un clone est appelé, se charger d'empiler le travail en cours pour instancier un nouveau travail). Donc chaque fois qu'on a un problème à résoudre, on essaye d'abord de voir si on peut s'en passer avant de se résoudre à y recourir
    Exemple de factorielle sans récursivité
    Code c :
    1
    2
    3
    4
    5
    6
    7
    unsigned long fact(unsigned short n)
    {
        unsigned long res;
        if (n < 2) return 1;
        for (res=1; n > 1; res*=n, n--);
        return res;
    }
    Toutefois même si le tri rapide est possible sans récursivité, c'est super compliqué à faire ainsi (en fait on simule la récursivité en mettant nous-même en mémoire la position en cours dans le tableau pour travailler sur des parties plus petites) donc dans ton cas, la récursivité reste obligatoire. Cependant je ne sais pas s'il s'agit d'un TP à faire ou si c'est juste pour le plaisir mais dans les deux cas tu as beaucoup de lacunes à combler (comme simplement le fait de savoir parcourir un tableau quand il faut traiter ses éléments).
    Plus d'infos sur ton algo ici => http://fr.wikipedia.org/wiki/Tri_rapide
    Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
    Tout ce qu'un individu reçoit sans rien faire pour l'obtenir, un autre individu a dû travailler pour le produire sans en tirer profit.
    Tout Pouvoir ne peut distribuer aux uns que ce qu'il a préalablement confisqué à d'autres car on n'accroît pas les biens en les divisant.
    Quand la moitié d'un peuple croit qu'il ne sert à rien de faire des efforts car l'autre moitié les fera pour elle, et quand cette dernière moitié se dit qu'il ne sert à rien d'en faire car ils bénéficieront à d'autres, cela s'appelle le déclin et la fin d'une nation.
    Dr. Adrian Rogers (1931-2005)

  3. #3
    Invité de passage
    Femme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 6
    Points : 3
    Points
    3

    Par défaut

    Bonsoir,

    Tout d'abord merci pour votre réponse très complète et qui m'a été très utile.

    Cet exercice, je l'effectue de ma propre volonté pour m’entraîner à programmer en C.

    Mais en effet, je me rend compte qu'au final me manque plusieurs notions avant de pouvoir l'aborder.

    J'ai bien compris tout ce que vous m'avez expliquer, et je vais étudier sa de très près.

    Concernant la récursivité, on l'a pas encore traité en cours. Mais je vais y travailler dessus.

    Avant de repasser à cet exercice, je pense qu'il serait plus judicieux que je fasse d'autres exercices, étape par étape, jusqu'à que j'ai toutes les connaissances pour cet exercice la.

    Merci pour le lien concernant l'algorithme du tri rapide, maintenant j'ai vraiment bien compris le procédé du tri rapide. Me reste plus qu'à le transcrire en C !

    Je vous remercie pour toute votre aide.
    Bonne soirée à vous

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •