tri par selection recursif

**valanscu77** · 17/03/2007, 19h27

Bonjour tout le monde,

voila j'ai un problème avec la récursivité. Je suis censé programmer un tri par sélection de manière récursive mai je vois pas du tout comment faire. Est ce que quelqu'un pourrai m'expliquer en gros la logique d'un tel tri?

merci beaucoup

**millie** · 17/03/2007, 19h38

Tu peux regarder ici :

http://algo.developpez.com/

Notamment ici :
http://algo.developpez.com/sources/?...#tri_selection

**koala01** · 18/03/2007, 07h09

Salut,

La première chose à savoir, c'est que la récursivité peut, tres souvent, etre remplacée intelligemment par une boucle qui fera le travail

Evidemment, si c'est pour un travail scolaire, ou dans d'autres circonstances, on peut aussi etre tenu d'appliquer la récursivité, alors qu'il serait vraissemblablement plus facile de faire sans... Donc... il est peut etre intéressant de rappeler ce qu'est la récursivité, et comment arriver à l'envisager sereinement

La récursivité, c'est quoi

c'est tout simplement une fonction qui est en mesure de s'appeler elle-même.

Le problème, c'est que si la fonction s'appelle elle-même, elle risque fort de le faire "ad-vitam", et donc qu'il faut trouver le moyen pour que, quoi qu'il arrive, elle finisse par se trouver dans une situation où elle arretera de le faire.

Cette situation dans laquelle la fonction ne se rappellera plus elle-meme est ce que l'on nomme "le cas de base", et l'ensemble des parametres passés à la fonction n'aura qu'un seul but: atteindre ce "cas de base".

Typiquement, l'action qui sera effectuée dans le cas de base est relativement simple: soit on en fait purement et simplement rien (si la fonction ne doit renvoyer aucune valeur), soit, on renvoit la valeur "de base" (celle qui permettra, de proche en proche, de calculer la suite)

Le gros du travail consiste donc, finalement, à pas grand chose:

déterminer le cas de base
déterminer le moyen d'atteindre le cas de base
savoir comment modifier le cas de base pour pouvoir le renvoyer à l'appel précédent...

L'algorithme générique est du genre de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
type_renvoi FonctionRecursive(argument,(...))
|    si( cas de base atteint)
|    |    renvoyer valeur de base
|    sinon
|    |    (actions à prendre avant appel à la récursivité)
|    |    variable= FonctionRecursive(argument modifié,(...))
|    |    (actions à prendre apres appel à la récursivité)
|    |    renvoyer la valeur récupérée modifiée s'il échoit
|    fin si

Deux exemples, parfaitement inutiles (hormis leur coté didactique) de récursivité seraient le calcul de l'élévation à l'exposant N d'une valeur et celui de la factorielle d'un nombre:

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
 
entier Factorielle(entier nombre)
|   @ la factorielle est la multiplication de l'ensemble des chiffres
|   @ non nuls qui précedent le nomre donné (le nombre donné inclu)
|   cas de base: nombre =1
|   si nombre =1
|   |   renvoie nombre
|   sinon
|   |   @ pour atteindre le cas de base, on passe nombre -1 à la fonction
|   |   @ et on se sert du retour de la fonction comme multiplicateur du 
|   |   @nombre
|   |   retour=Factorielle(nombre -1)
|   |   retour= retour x nombre
|   |   renvoie retour
|   fin si
 
 
 
entier Exposant(entier nombre, entier exp)
|   @Pour calculer l'exposant on multiplie nombre par lui meme exp fois
|   @d'affilée
|   @cas de base: exp =0 (n'importe quoi exposant 0= 1 :D)
|    si exp = 0
|    |    renvoie 1
|    sinon
|    |    @pour atteindre le cas de base, on soustrait 1 à exposant
|    |    retour=Exposant(nombre,exp-1)
|    |    @ on multiplie retour par nombre
|    |    retour=retour x nombre
|    |    renvoye retour
|    fin si

Pour le problème qui t'intéresse, il nous manque trois données primordiales pour te répondre correctement: ce que tu dois trier, l'ordre de tri et le critère de tri...

En effet, les actions à mener pour tendre vers le cas de base et le cas de base seront vraissemblablement différentes si tu dois simplement trier un tableau ou si tu dois trier une structure dynamique (liste ou arbre binaire/naire), si tu dois les trier par ordre croissant ou décroissant et si le tri doit s'effectuer sur un critère ou sur plusieurs critères, ce qui influencera fortement l'algorithme à mettre au point...

Si, apres ces explications, la récursivité n'est pas claire pour toi, tu peux toujours passer sur ==>cette page<== où elle est expliquée en long, en large et en travers.

Retiens également que la création de l'algorithme vient apres une étape primordiale: l'expression claire nette et concise des besoins de l'application à concevoir...

Or, tu avoueras que

un tri par sélection de manière récursive

fait un peu léger comme expression de ce qu'il te faut

En plus, il n'est pas d'usage sur ce forum de faire tout le travail à ta place: c'est le pire des services que l'on puisse te rendre, car cela mene bien souvent à faire quelque chose que tu n'aurais peut etre pas compris...

Si tu as un problème de compréhension sur un point bien précis, n'hésite pas à poser la question

Si tu as un problème à un moment bien précis de l'algorithme, montre nous ce que tu as déjà fait, et indique nous le problème que tu n'arrive pas à résoudre

Ce n'est qu'ainsi que tu obtiendras une aide à la fois efficace (pour résoudre ton problème) et utile (pour te permettre de comprendre et d'adapter la solution par la suite

**Rakken** · 19/03/2007, 15h53

/me se souvient avec emotion de son premier algo récursif.

C'était a mes débuts en progs, et avec mon binôme de l'époque on devait colorier une zone (pour refaire un paint). Il fallait donc parcourir (et stocker) tous les points pour changer leur couleurs.
C'était en turbo pascal, et ca a été mon premier bug vraiment difficile à corriger "Stack overflow error"

. L'algo était nickel sur le papier, mais une fois implémenté, la mémoire explosait pour des images plus grande que... 2cm² sur l'écran. J'ai refait l'algo differement, et on a pu colorier une image un peu plus grande, mais ca explosait toujours dans certains cas (genre colorier une image completement blanche).
Pour finir un prof nous a expliqué que la plupart du temps, un algo récursif peut se faire avantageusement remplacer par un while, et la, plus de soucis de mémoire ;-)

Sinon, pour revenir a ton problème, ben... je crois pas pouvoir en dire beaucoup plus que Koala01. Montre nous ce que tu as déjà ou ce qui te pose problème pour commencer et on verra ce qu'on peut faire ^_^

**naruto70** · 05/11/2007, 19h50

Bonjour
Je suis désolé. Je sais que ce post est assez vieux mais c'est exactement ce que je cherche ( ou presque ).
Il faut que je fasse un tri par sélection de manière récursive. Il faut que je tri un tableau à indice simple dans l'ordre croissant.

ce que tu dois trier, l'ordre de tri et le critère de tri...

Je suis pas sur de savoir ce qu'est le critère de tri mais bon...
Je ne recherche pas du code mais plutot la logique. Je ne vois pas ce que peut être le cas de base à retourner. Est-ce que le programme est aussi court que pour calculer une factoriel ( avec un si ... sinon... et 2 instructions seulement ) ? Ou est-ce qu'il faut développer un peu plus ?

Merci

**Rakken** · 06/11/2007, 11h12

Je suis pas sur de savoir ce qu'est le critère de tri mais bon...

Le critère de tri, c'est la méthode que tu utilises pour savoir quel élément est supérieur a un autre. Pour faire un cas simple
"aaaa" "b".
Si le critère de tri est l'ordre alphabétique, le "aaaa" arrive en premier.
Si le critère est le nombre de lettres, alors "b" arrive en premier.

Sinon pour revenir plus précisement a ta question, si je me souvient bien de mes cours d'algo, dans un tri par selection, du doit trouver l'élément le plus grand, le mettre a la fin du tableau et recommencer.
Intuitivement, ce que je ferai (ca n'est probablement pas optimal) c'est une fonction avec le tableau a trier en parametre. Premiere itération, je recherche l'élément le plus grand, je le sauve, puis je relance la fonction avec le même tableau moins l'élément que je vient de trouver (genre du peux passer l'élément a -1 si tu ne teste que des entiers positifs, ou autres astuces du genre) puis je continue jusqu'a ce qu'il ne reste plus que les éléments "éliminé" dans le tableau.
Ensuite je dépile, donc je retourne un tableau avec en derniere position l'élément que je viens de trouver (ici on est au niveau le plus profond, donc le tableau ne contient qu'un seul élément, le plus petit du tableau). Puis on remonte d'un niveau, et je retourne le tableau que j'ai récupéré avant, après avoir rajouté en derniere position l'élément trouvé a ce niveau, et ainsi de suite.
Et au final on se retrouve avec un tableau trié par ordre croissant ;-)

**naruto70** · 06/11/2007, 13h58

Merci je commence à y voir un peu plus clair.
Mais quand tu dis qu'il faut savegarder l'élément, tu le sauvegarde comment ?

J'ai essayé un programme :

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
void triSelection( int tableau[], int comparaison )
{
    int temp; int Pmax; int max = tableau[0];
    if ( comparaison > 0 )
    {
        for ( int i = 0; i < comparaison; i++ )
        {
            if ( max < tableau[i] )
            {
                max = tableau[i];
                Pmax = i;
            }
            else
                continue;
        }
        temp = tableau[Pmax];
        tableau[Pmax] = tableau[comparaison];
        tableau[comparaison] = temp;
        triSelection( tableau, comparaison - 1 );
    }
}

Au premier appel, je cherche dans le tableau la valeur maximale avec la boucle for. max étant la valeur maximale et Pmax la position de la valeur maximale. Une fois que j'ai trouvé dans le tableau la valeur max, je l'intervertis avec la dernière valeur du tableau grâce à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
        temp = tableau[Pmax];
        tableau[Pmax] = tableau[comparaison];
        tableau[comparaison] = temp;
        triSelection( tableau, comparaison - 1 );

Puis je rappelle la fonction avec pour arguments le tableau puis comparaison - 1, c'est à dire qu'au prochain appel, la fonction va recherché la valeur la plus grande sans tenir compte de la dernière case.
Avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( comparaison > 0 )

si comparaison vaut 0, alors c'est que le tableau est trié. Le code est en c++, normalement les tableaux sont appelés par référence, il est directement modifié depuis la fonction principal.
Le compilateur compile ( c'est pas terrible à dire mais je sais pas comment dire autrement

) mais lors de l'execution du programme, il met un message d'erreur et se ferme. Je ne pense pas que se sois la mémoire puisque j'ai essayé avec un tableau de 5 éléments. J'ai pas fait exactement comme tu m'a expliqué, mais ton expliquation m'a bien aidé quand même.
Si on pouvais m'expliqué où le programme bogue.

merci.

**koala01** · 06/11/2007, 16h37

Quand on travaille avec des tableaux en C et en C++, il est primordial de garder une information en tête: les index commencent à 0.

Cela signifie que si tu as un tableau de N élément, le dernier index valide est N-1

Dés lors, il faut décider de la signification que l'on donne au deuxième paramètre de la fonction:

Soit, il s'agit du nombre d'éléments qu'il reste à trier,
Soit il s'agit de la valeur du dernier index valide à tester

Généralement, on optera pour la première solution... Mais cela sous entend que, chaque fois que l'on fera appel à la valeur fournie, l'index correspondant sera cette valeur - 1...

Avant d'écrire la première ligne de code, il est - comme toujours - nécessaire de réfléchir correctement à l'ensemble de ce qui doit être fait...

Il faut commencer par réfléchir aux informations qui doivent être fournies à la fonction, et à ce qu'elle doit renvoyer.

Ce qu'elle doit renvoyer, c'est relativement simple: il s'agit d'un pointeur sur le premier élément du tableau...

Ce qu'il faut lui fournir comme paramètres, ce n'est pas beaucoup plus compliqué:

un pointeur sur le premier élément du tableau
le nombre (sous la forme d'un entier - tant qu'à faire - non signé) d'éléments à prendre en compte

Ce qui nous donnera une fonction dont le prototype sera de l'ordre de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int* TriParSelection(int* tab, size_t count)

Comme tu semble d'avis de partir sur une optique récursive, il faut donc réfléchir au cas de base.

Il n'est pas bien compliqué à saisir: s'il n'y a qu'un seul élément à tester, le travail est fini

On partirait donc sur un algorithme dont la base serait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
int* TriParSelection(int* tab, size_t count)
|    SI count = 1
|    |    renvoie tab
|    SINON
|    |    tri de tab
|    |    tab <-- TriParSelection(tab, count-1)
|    |    renvoie tab
|    FIN SI

La logique de la fainéantise nous incitera cependant, étant donné qu'il faut renvoyer tab de toutes manières, à inverser le test, et à transformer l'algorithme en

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int* TriParSelection(int* tab, size_t count)
|    SI count <> 1
|    |    tri de tab
|    |    tab <--TriParSelection(tab, count-1)
|    FIN SI
|    renvoie tab

Mais, il y a toujours une étape qui reste très floue: c'est "tri de tab"...

La question que l'on se posera fatalement, c'est "Comment trier tab"

la réponse tient en une simple boucle et une inversion:

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
 
tri de tab
|    @ on décide arbitrairement que l'index auquel se trouve l'élément maxima
|    @ est l'index 0
|    size_t ind <-- 0
|    @ on parcoure le tableau pour trouver le vrai maximum
|    Pour i = 0 à count
|    |    SI tab[i] > tab[ind] 
|    |    |    ind <-- i
|    |    FIN SI
|    FIN POUR
|    @ et on inverse les deux index
|    tab[count - 1] <-- tab[count - 1] XOR tab[ind]
|    tab[ind] <-- tab[ind] XOR tab[count - 1]
|    tab[count - 1] <-- tab[count - 1] XOR tab[ind]

En remplaçant "tri de tab" par cette partie d'algorithme, on en arrive à l'algorithme final

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int* TriParSelection(int* tab, size_t count)
|    SI count <> 1
|    |    size_t ind <-- 0
|    |    Pour i = 0 à count
|    |    |    SI tab[i] > tab[ind] 
|    |    |    |    ind <-- i
|    |    |    FIN SI
|    |    FIN POUR
|    |    tab[count - 1] <-- tab[count - 1] XOR tab[ind]
|    |    tab[ind] <-- tab[ind] XOR tab[count - 1]
|    |    tab[count - 1] <-- tab[count - 1] XOR tab[ind]
|    |    tab <--TriParSelection(tab, count-1)
|    FIN SI
|    renvoie tab