Un des algorithmes de tri les plus simples à appréhender est celui du tri à bulles. Il consiste à balayer la liste autant de fois qu’il y a d’éléments, et à chaque passage de faire remonter en fin de liste les plus grands éléments détectés. C’est également l’algorithme le plus lent.
Fonctionnement de l’algorithme de tri à bulles
Je vous propose une implémentation qui comporte des exemples d’utilisation des instructions COBOL suivantes :
- Tableaux à taille dynamique : OCCURS … DEPENDING ON…
- Boucles avec test à la fin : PERFORM WITH TEST AFTER
- Double boucle imbriquée faisant varier deux indices : PERFORM VARYING … AFTER …
******************************************************************
* Component : BBUBSORT (COBOL batch)
* Author : Cyril Coquilleau
* Date : 2018-04-14
* Purpose : Implements bubble sort algorithm
******************************************************************
IDENTIFICATION DIVISION.
PROGRAM-ID. BBUBSORT.
DATA DIVISION.
WORKING-STORAGE SECTION.
*Array definition
01 ARRAY-SIZE PIC 9(9) VALUE 10000.
01 ELT-ARRAY OCCURS 0 TO 9999999 DEPENDING ON ARRAY-SIZE.
03 ELT-VALUE PIC 9(8).
*Indexes
01 POS PIC 9(9).
01 I PIC 9(9).
01 J PIC 9(9).
01 J-PLUS1 PIC 9(9).
*Temporary data for swapping
01 ELT-VALUE-TEMP PIC 9(8).
PROCEDURE DIVISION.
MAIN-PROCEDURE.
PERFORM VARYING POS FROM 1 BY 1 UNTIL POS > ARRAY-SIZE
COMPUTE ELT-VALUE(POS) = 1 + FUNCTION RANDOM * 10000000
DISPLAY ELT-VALUE(POS)
END-PERFORM
* Sorting the array with Bubble Sort algorithm
PERFORM WITH TEST AFTER
VARYING I FROM ARRAY-SIZE BY -1 UNTIL I=2
AFTER J FROM 1 BY 1 UNTIL J = I - 1
COMPUTE J-PLUS1 = J + 1
* Swapping if needed
IF ELT-VALUE(J-PLUS1) < ELT-VALUE(J)
MOVE ELT-VALUE(J-PLUS1) TO ELT-VALUE-TEMP
MOVE ELT-VALUE(J) TO ELT-VALUE(J-PLUS1)
MOVE ELT-VALUE-TEMP TO ELT-VALUE(J)
END-IF
END-PERFORM
PERFORM VARYING POS FROM 1 BY 1 UNTIL POS > ARRAY-SIZE
DISPLAY ELT-VALUE(POS)
END-PERFORM
STOP RUN.
END PROGRAM BBUBSORT.