Discussion :

[patrick974]

Bonjour tout le monde.
Je suis en train d'implémenter tous les algorithmes de tri par bulle, ou plutôt les principaux algorithmes de tri. J'ai déjà implémenté le tri par permutation, le tri par recherche du minimum et le tri par insertion.
Je dois maintenant implémenter le tri par bulle avant de m'attaquer au tri rapide et au tri par fusion.
J'ai écrit un morceau de code pour ce tri, mais il ne fonctionne pas. J'ai pourtant l'impression que mes prédicats sont corrects, et je n'arrive pas à comprendre mes erreurs.
Je n'ai malheureusement trouvé aucune discussion à ce sujet sur le forum. Pourriez-vous m'aider s'il vous plaît.
Voici le code que j'ai écrit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
% Tri par bulle
bubblesort([],[]).
bubblesort([X],[X]).
bubblesort([X|Xs],[Z|Zs]) :-
	bubblesort(Xs,Zs),
	bubble([X|Xs],[Z|Zs]).
bubble([X],[X]).
bubble([X,Y|Xs],[Y,X|Zs]) :-
	bubble([X|Xs],[X|Zs]),
	X>Y.
bubble([X,Y|Xs],[X,Y|Ys]) :-
	bubble([Y|Xs],[Y|Ys]),
	X=<Y.

Je vous remercie.
Au revoir.

[Trap D]

Sans rentrer dans le détails, je crois que ces deux clauses devraient être modifiées

Code :

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

1
2
3
4
5
6
bubble([X,Y|Xs],[Y,X|Zs]) :-
	bubble([X|Xs],[X|Zs]),
	X>Y.
bubble([X,Y|Xs],[X,Y|Ys]) :-
	bubble([Y|Xs],[Y|Ys]),
	X=<Y.

AMA les tests devraient être effectués avant les appels à bubble.
Les deux tests s'excluant, si le premier est faux le second est vrai.
Un coupe-choix après le premier test serait utile.
Donc on peut sans doute les réécrire de cette façon :

Code :

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

1
2
3
4
5
bubble([X,Y|Xs],[Y,X|Zs]) :-
        X > Y, !,
	bubble([X|Xs],[X|Zs]).
bubble([X,Y|Xs],[X,Y|Ys]) :-
	bubble([Y|Xs],[Y|Ys]).

Ceci dit, ce n'est pas testé.

[patrick974]

Bonjour,
j'ai essayer de voir un peu comment marche le mode trace de prolog. C'est pas super compliqué, mais vachement décourageant je trouve ....

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
 
[trace] 16 ?- bubble([1,3,2,1,5],Z).
   Call: (7) bubble([1, 3, 2, 1, 5], _G516) ? creep
^  Call: (8) 1>3 ? creep
^  Fail: (8) 1>3 ? creep
   Redo: (7) bubble([1, 3, 2, 1, 5], _G516) ? creep
   Call: (8) bubble([3, 2, 1, 5], [3|_G599]) ? creep
   Call: (9) bubble([2, 1, 5], [2|_G608]) ? creep
   Call: (10) bubble([1, 5], [1|_G617]) ? creep
   Call: (11) bubble([5], [5|_G626]) ? creep
   Exit: (11) bubble([5], [5]) ? creep
   Exit: (10) bubble([1, 5], [1, 5]) ? creep
   Exit: (9) bubble([2, 1, 5], [2, 1, 5]) ? creep
   Exit: (8) bubble([3, 2, 1, 5], [3, 2, 1, 5]) ? creep
   Exit: (7) bubble([1, 3, 2, 1, 5], [1, 3, 2, 1, 5]) ? creep
 
Z = [1, 3, 2, 1, 5] 
 
Yes

En fait, le probleme vient de l'appel récursif sur bubble([X|Xs],[X|Zs]). Cet appel fait que prolog, va directement au predicat bubble([X,Y|Xs],[X,Y|Ys]) :- bubble([Y|Xs],[Y|Ys]). et tourner en boucle sur ce meme prédicats, jusqu'à ce qu'il trouve la condition d'arrêt, qui est bubble([X],[X]).
La suite, elle est évidente ...
Donc je vais essayer de trouver une solution à ce problème !!

Merci,
au revoir.

[Trap D]

Il me semble que dans le tri bulle, on utilise un flag indiquant si une inversion a été faite ou pas pendant le parcours.
je n'en vois pas dans ton code et je pense qu'il serait nécessaire qu'il y en ait un.
Perso, je viens d'implémenter le tri bulle en utilisant ce flag.

[patrick974]

Bonjour.
Je suis désolé de répondre tardivement. Le boulot ...
J'ai eu un peu de temps libre pour continuer a travailler sur mon tri par bulle. J'ai pu écrire la fonction bubble. Il ne me reste plus qu'à écrire une fonction bubblesort qui va se charger d'appliquer bubble aux n premiers éléments de la liste, puis aux n-1 premiers, puis ...
Tu avais raison, il faut bien utiliser un flag pour cet algorithme. En tout cas j'en ai utilisé un pour la fonction bubble. On verra bien pour la suite.
Donc voilà le code pour ma première fonction, pourrai tu me dire ce que tu en penses ?
Je l'ai testé, elle marche normalement selon moi. Le truc qui cloche, c'est que j'ai l'impression d'avoir un peu bidoullé !

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
 
% la deuxieme liste sert stocker
bubble([X],Ss,R) :-
    append(Ss,[X],Z),
    invl(Z,R).
 
bubble([X,Y|Xs],Ss,R) :-
    X=<Y, % flag
    append(Ss,[X],NSs),
    bubble([Y|Xs],NSs,R).
 
bubble([X,Y|Xs],Ss,R) :-
    Y<X, % flag
    append(Ss,[Y],NR),
    bubble([X|Xs],NR,R).
% pour placer le dernier element de la liste
invl([X,Y],[Y,X]) :-
    X>Y.
invl([X,Y],[X,Y]).
invl([X|Xs],[X|Ys]) :-
    invl(Xs,Ys).

Merci, et au revoir.

[patrick974]

Bonjour,
j'ai enfin terminé l'implémentation du tri par bulle. J'ai du légèrement modifier le code de la fonction bubble d'avant. Donc voila le code, ça poura peut être servir à quelqu'un plus tard.

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
 
% Tri par bulle
bubblesort([X],[X]).                      
bubblesort([X|Xs],L) :-
    bubblesort(Xs,Ys),
    bubble([X|Ys],[],Z,D),
    append(Z,[D],L).
 
bubble([X],Ss,R,D) :-
    append(Ss,[X],Z),
    invl(Z,R,D).
 
bubble([X,Y|Xs],Ss,R,D) :-
    X=<Y,
    append(Ss,[X],NSs),
    bubble([Y|Xs],NSs,R,D).
 
bubble([X,Y|Xs],Ss,R,D) :-
    Y<X,
    append(Ss,[Y],NR),
    bubble([X|Xs],NR,R,D).
 
invl([X,Y],[Y,X],X) :-
    X>Y.
invl([X,Y],[X,Y],Y).
invl([X|Xs],[X|Ys],D) :-
    invl(Xs,Ys,D).

Si quelqu'un a une meilleur solution, ou une autre solution, j'aimerai bien la voir. Si vous voulez des commentaires ou des explications, faîtes le moi savoir.
Merci pour ton aide Trap D.
Au revoir.

[Trap D]

Salut

Maintenant que tu as terminé, je "publie" ma version :
Elle est basée sur le parcours de la liste des éléments à trier (prédicat une_bulle) , si je fais une inversion, je mets un flag à 1.
Ce parcours est répété tant que le flag est à 1.
La liste issue d'un parcours est construite en sortie de récursion.

Code prolog :

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
% une_bulle(+Liste_a_trier, -Flag, -Liste_triee).
 
% Si je n'ai qu'un élément, 
% la liste est triée et je n'ai pas d'interversion
une_bulle([X], 0, [X]).
 
% Si le nombre à gauche est plus grand que le nombre à droite
% J'ai une interversion, donc le flag est à 1
% Le nombre à droite est interverti avec le nombre à gauche
% et donc placé à gauche de la liste restant à trier (à laquelle j'ajoute X)
% Je n'ai pas à m'occuper du flag d'interversion de la liste restant à trier
une_bulle([X, Y | R], 1, [Y | L]) :-
	X > Y, !,
	une_bulle([X | R], _A, L).
 
% Il n'y a pas d'intervertion, donc le flag résultant de cette étape
% est identique au flag issu du parcours du reste de la liste
une_bulle([X, Y | R], A, [X | L]) :-
	une_bulle([Y | R], A, L).
 
% Le tri bulle par lui même
% tri_bulle(+Liste_a_trier, -Liste_triee).
 
% si le flag est 0, c'est fini
% sinon on repart pour un tour
tri_bulle(L1, L) :-
	une_bulle(L1, A, L2),
	(   A == 0, L = L2 ; tri_bulle(L2, L)).

[patrick974]

Bonjour,
merci pour ta solution.
C'est toujours très interessant d'être confronté à une autre manière de penser et de coder. Ton code est vachement plus optimisé que le mien, et en plus je trouve qu'il est beaucoup plus facile à comprendre !
En plus je savais pas qu'on pouvais faire un if then else en prolog (enfin si, mais avec le ! ), du coup j'ai appris un nouveau truc .
Au revoir.