Bubble Tri
tri par bulles

GW-Basic, utilisé par PC-Basic

Programme avec Texte Seulement

PC-BASIC

Il existe un certain nombre d'algorithmes courants pour trier les éléments d'une liste. Le tri shell, le tri cubes, le tri en tas, le tri par fusion, le tri par arbre binaire et le tri par bulles ne sont qu'une poignée d'entre eux.

Le Bubble Tri par exemple, compare des ensembles de deux éléments dans une liste qui sont adjacents. Si le premier élément de l'ensemble est plus grand que le second, les éléments de l'ensemble sont permutés ; sinon, rien n'est fait.

Ensuite, l'algorithme passe à l'ensemble suivant de deux éléments de la liste, et la même comparaison est effectuée. Lorsque plus aucun échange n'est nécessaire entre tous les ensembles d'éléments adjacents, l'algorithme se termine car la liste est complètement triée (par ordre croissant).

BUBBLE1.BAS implémente un tri à bulles avec au plus 100 éléments. Vous êtes invité à entrer des nombres positifs, un à la fois, à partir d'une liste (dans n'importe quel ordre, évidemment). La saisie d'un nombre négatif signalera la fin de la liste. Enfin, votre liste dans l'ordre où elle a été entrée, à côté de la liste dans l'ordre croissant, s'affichera à l'écran.

Sans l'utilisation de tableaux, le programme serait beaucoup plus difficile à construire (et peu élégant). Les tableaux offrent la flexibilité de comparer les ensembles d'éléments adjacents - voir les lignes 90, 95 et 96 pour les comparaisons conditionnelles. Observez également les multiples boucles FOR/NEXT : les boucles continuent de s'exécuter jusqu'à ce que la liste entière soit complètement triée.

Étant donné qu'un nombre négatif interrompt l'entrée d'éléments de liste, aucun nombre négatif n'est autorisé en tant qu'éléments de liste. Peut-être qu'au lieu d'un nombre négatif signifiant la fin de la liste, un seul nombre - positif ou négatif - pourrait être le "numéro d'arrêt" attribué. Mais alors, bien sûr, ce numéro d'arrêt ne serait pas non plus autorisé en tant qu'élément de liste.

10 KEY OFF:SCREEN 9:COLOR 15,1:CLS
20 DIM ARRAY(100):TEMP=0
25 PRINT "Nombre maximal d'entrées: 100."
30 FOR DUMMY=1 TO 100
40 PRINT "Input Value #(";DUMMY;") -->(-1 pour arrêter)";: INPUT A
45 IF A=-1 THEN 65
50 ARRAY(DUMMY)=A
60 NEXT DUMMY
65 CLS:PRINT "Liste originale: "
66 FOR LA=1 TO (DUMMY-1):PRINT ARRAY(LA);" ";:NEXT LA
70 FOR D=l TO (DUMMY-2)
80 FOR GA=1 TO (DUMMY-2)
90 IF ARRAY(GA)>ARRAY(GA+1) THEN 100
95 IF ARRAY(GA)<ARRAY(GA+1) THEN 200
96 IF ARRAY(GA)=ARRAY(GA+1) THEN 200
100 TEMP=ARRAY(GA):ARRAY(GA)=ARRAY(GA+1):ARRAY(GA+1)=TEMP
110 GOTO 200
200 NEXT GA
210 NEXT D
220 PRINT:PRINT
230 PRINT"Liste triée: "
240 FOR LA=1 TO (DUMMY-1):PRINT ARRAY(LA);" ";:NEXT LA

Version avec SWAP

5 REM Bubble - Sort
10 DIM A(6)
20 A(1)=12:A(2)=5:A(3)=1
30 A(4)=23:A(5)=11:A(6)=3
40 FLIPS=1
50 IF FLIPS=0 THEN 110
60 FLIPS=0
70 FOR N=1 TO 5
80 IF A(N)>A(N+1) THEN SWAP A(N), A(N+1): FLIPS=1
90 NEXT N
100 GOTO 50
110 FOR N=1 TO 6
120 PRINT A(N),
130 NEXT N

Version avec une boucle WHILE-WEND et SWAP

5 REM Bubble - Sort
10 DIM A(6)
20 A(1)=12:A(2)=5:A(3)=1
30 A(4)=23:A(5)=11:A(6)=3
40 FLIPS=1
50 WHILE FLIPS
60 FLIPS=0
70 FOR N=1 TO 5
80 IF A(N)>A(N+1) THEN SWAP A(N), A(N+1): FLIPS=1
90 NEXT N
100 WEND
110 FOR N=1 TO 6
120 PRINT A(N),
130 NEXT N