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

  1. #1
    Nouveau Candidat au Club
    Comment écrire un pseudo code en langage C
    Bonjour,
    Je viens tout juste de finir mon premier cours en langage C. Dans le cadre de mon apprentissage, j'ai un exercice que je n'arrive pas à résoudre et dont l'intitulé est donné ci-dessous.
    Pouvez vous m'aider s'il vous plaît ?

    Soit i, l’index d’un élément dans le tableau A. L’algorithme consiste à trouver la position finale
    de l’élément A[i] en comptant les valeurs inférieures à cet élément. Si A[i] n’est pas à la bonne
    place—appelons k sa position dans le tableau trié—, on échange A[i] et A[k] et on recommence en
    cherchant la position du nouvel élément à la position i. Une fois qu’il n’y a plus de permutation
    (k = i), l’algorithme continue avec i = i + 1. Initialement i = 1.

  2. #2
    Expert éminent
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
        size_t it, it_count, count, val;
     
        for(it=1; it < nb_elts; ++it) {
            do {
                 for(val=tab[it], it_count=0, count=0; it_count < nb_elts; ++it_count) {
                     if (/*(it_count != it) &&*/ (val > tab[it_count])) { ++count; }
                 }
     
                 if (count != it) { // swap tab[it] && tab[count]
                     tab[it]    = tab[count];
                     tab[count] = val;
                 }
            } while(it != count);
        }


    Édit :
    • "l’algorithme continue avec i = i + 1. Initialement i = 1" et "Soit i, l’index d’un élément dans le tableau A" : décrit une boucle pour (ligne 3), mais ne donne pas la borne supérieure. On peut penser qu'elle va parcourir tout le tableau et donc comme elle commence à 1, peut inclure cette borne (test soit < soit <=)
    • "en comptant les valeurs inférieures à cet élément" : décrit une boucle pour (ligne 5), qui parcourt tout le tableau pour faire le comptage
    • "on recommence en cherchant la position du nouvel élément à la position i" : décrit une boucle tant que faire ou faire tant que (ligne 4), avec comme test de fin "Une fois qu’il n’y a plus de permutation (k = i)"
    • "on échange A[i] et A[k]" : décrit un échange (ligne 9) le classique de l'algo

  3. #3
    Nouveau Candidat au Club
    Merci pour votre réponse
    Bonjour foetus,

    Je vous adresse un grand merci pour le temps et les orientations que vous m'avez accordé dans la résolution de ce problème.

    Vos explications sont assez développées et me permettent de mieux comprendre comment j'aurais dû procéder ; un grand merci pour la pédagogie utilisée.

    Au plaisir,

    Romaric,

  4. #4
    Expert éminent
    Quelques oublis

    À la ligne 6, on ne teste pas si on n'est sur la case i, parce que le test inférieur est strict ((val > tab[it_count])). Si on doit également tester l'égalité, il faudra sûrement exclure la case i du comptage.

    D'ailleurs, 1 autre truc, cet algo de tri ne semble pas stable (<- lien wiki en français) - c'est à dire si tu as 2 valeurs identiques, le tri n'est pas garanti.
    Donc, pour moi, c'est assez logique que, lors du comptage, on doit exclure la case i : mais je peux me tromper

    Et dernier point, ma variable count ne débordera pas parce qu'elle sera toujours inférieure à nb_elts, justement parce qu'on ne compte jamais la case i. Donc attention, si on doit compter également cette case i.
    Mais par contre , cette variable count peut être fausse, parce qu'en C, les indices de tableau commencent à 0 et le comptage lui à 1.

  5. #5
    Nouveau Candidat au Club
    Merci pour votre réponse
    Re-bonjour,

    Oui je pense en effet au vu de ce que vous avez proposé, que cet algo n'est pas stable. Puisque je dois comparer le résultat de cet algo avec celui du QuickSort et du HeapSort .

    J'aurais l'occasion de vérifier cette stabilité lorsque je vais l'exécuter.

    Merci bien pour le lien sur le tri que vous avez mis dans votre réponde précédente;

    Bien à vous,

    Romaric,

  6. #6
    Expert éminent sénior
    Bonjour
    Citation Envoyé par tekeuhtsafackromaric Voir le message
    Oui je pense en effet au vu de ce que vous avez proposé, que cet algo n'est pas stable. Puisque je dois comparer le résultat de cet algo avec celui du QuickSort et du HeapSort .

    J'aurais l'occasion de vérifier cette stabilité lorsque je vais l'exécuter.
    La stabilité d'un tri ce n'est pas comparer ses performances avec un autre tri, c'est pouvoir assurer que 2 éléments égaux resteront dans le même ordre l'un par rapport à l'autre à la fin du tri.
    Exemple: si on a un jeu de cartes et qu'on veut le trier par valeurs sans se préoccuper des couleurs, alors si le valet de trèfle est avant le valet de carreau avant le tri, un tri stable garantira sa position avant le valet de carreau après le tri. Un tri instable ne garantit pas ce résultat.
    qsort n'est pas un tri stable. heapsort j'en sais rien. Et ton algo lui il sera stable si tu utilises un test "<" pour comparer et instable si tu utilises un test "<=".
    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