Discussion :

[tekeuhtsafackromaric]

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.

[foetus]

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

[tekeuhtsafackromaric]

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,

[foetus]

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.

[tekeuhtsafackromaric]

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,

[Sve@r]

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.

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 "<=".