Implémentation de l’algorithme de tri Quicksort en COBOL

Un classique de l’algorithmie est l’implémentation de la méthode de tri Quicksort. C’est une des plus performantes, et également une des plus complexes.

Explication animée du fonctionnement de l'algorithme Quicksort
Fonctionnement de l’algorithme Quicksort

Pour vous entraîner, ou par challenge (kata code), vous pouvez le porter en langage COBOL. Cela vous permettra de mettre en oeuvre la récursivité ainsi que le passage de paramètres par référence et par valeur.

Je vous propose ci-dessous ma version de l’implémentation, avec le code en anglais pour que nos amis outre-atlantique puissent comprendre le code.
 
Tout d’abord le programme BTSTSORT d’alimentation du tableau et d’appel du module Quicksort :

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
32
33
34
35
36
37
38
39
40
     ******************************************************************
     * Component : BTSTSORT (COBOL batch)
     * Author : Cyril Coquilleau
     * Date : 2018-04-01
     * Purpose : Fills an array and launches Quicksort module
     ******************************************************************
       IDENTIFICATION DIVISION.
       PROGRAM-ID. BTSTSORT.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
     * Working data items
       01 ARRAY-SIZE   PIC 9(9) VALUE 10000.
       01 I            PIC 9(9).
       
     * Copy with the array to sort
       COPY 'CARRSORT.cpy'.

       PROCEDURE DIVISION.

       MAIN-PROCEDURE.
     *   Fills the array with random values    
          PERFORM VARYING I FROM 1 BY 1 UNTIL I > ARRAY-SIZE
             COMPUTE ELEMENT(I) = FUNCTION RANDOM * 10000000
          END-PERFORM
       
     *   Calls Quicksort module
          MOVE 1 TO LOW
          MOVE ARRAY-SIZE TO HIGH
          CALL 'MQCKSORT' USING REFERENCE ARRAY
                                CONTENT LOW
                                CONTENT HIGH
       
     *   Displays the sorted array    
          PERFORM VARYING I FROM 1 BY 1 UNTIL I > ARRAY-SIZE
             DISPLAY ELEMENT(I)          
          END-PERFORM            
           
          STOP RUN.
         
       END PROGRAM BTSTSORT.

 
Ensuite le module MQCKSORT implémentant l’algorithme Quicksort :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
     ******************************************************************
     * Component : MQCKSORT (COBOL Module)
     * Author : Cyril Coquilleau
     * Date : 2018-04-01
     * Purpose : Implements Quicksort algorithm  
     * Idea of algorithm : https://www.geeksforgeeks.org/quick-sort/
     ******************************************************************
       IDENTIFICATION DIVISION.
       PROGRAM-ID. MQCKSORT RECURSIVE.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
     * Partition Index
       01 PI             PIC 9(9).
       01 PI-MINUS1      PIC 9(9).
       01 PI-PLUS1       PIC 9(9).
       
     * Temporary data for PARTITION procedure
       01 PIVOT          PIC 9(9).
       01 I              PIC 9(9).
       01 I-PLUS1        PIC 9(9).
       01 J              PIC 9(9).
       01 ELEMENT-TEMP   PIC 9(9).

       LINKAGE SECTION.
       COPY 'CARRSORT.cpy'.

       PROCEDURE DIVISION USING ARRAY LOW HIGH.
       
       MAIN-PROCEDURE.
          IF LOW < HIGH
     *      Partitionning (fills PI data item)
             MOVE 0 TO PI
             PERFORM PARTITION
             COMPUTE PI-PLUS1 = PI + 1
             COMPUTE PI-MINUS1 = PI - 1
             
     *      Quicksort recursive calls
             CALL 'MQCKSORT' USING REFERENCE ARRAY
                                   CONTENT LOW
                                   CONTENT PI-MINUS1
             CALL 'MQCKSORT' USING REFERENCE ARRAY
                                   CONTENT PI-PLUS1
                                   CONTENT HIGH
          END-IF

          GOBACK
          .

       
       PARTITION.
          MOVE ELEMENT(HIGH) TO PIVOT
         
     *   Index of smaller element    
          COMPUTE I = LOW - 1
          PERFORM VARYING J FROM LOW BY 1 UNTIL J >= HIGH
     *      If current element is smaller than or equal to pivot
             IF ELEMENT(J) <= PIVOT
                COMPUTE I = I + 1
               
     *         Swap ELEMENT(I) and ELEMENT(J)
                MOVE ELEMENT(I)   TO ELEMENT-TEMP
                MOVE ELEMENT(J)   TO ELEMENT(I)
                MOVE ELEMENT-TEMP TO ELEMENT(J)
             END-IF
          END-PERFORM
         
     *   Swap ELEMENT(I+1) and ELEMENT(HIGH) (or pivot)
          COMPUTE I-PLUS1 = I + 1
          MOVE ELEMENT(I-PLUS1) TO ELEMENT-TEMP
          MOVE ELEMENT(HIGH)    TO ELEMENT(I-PLUS1)
          MOVE ELEMENT-TEMP     TO ELEMENT(HIGH)
     
     *   Returning the pivot position to the main procedure    
          MOVE I-PLUS1 TO PI
          .

       END PROGRAM MQCKSORT.

 
Et la copie CARRSORT permettant l’interfaçage entre les deux composants :

1
2
3
4
5
6
7
8
9
10
     ******************************************************************
     * Component : CARRSORT (COBOL Copybook)
     * Author : Cyril Coquilleau
     * Date : 2018-04-01
     * Purpose : Descripts the parameters for the Quicksort module
     ******************************************************************
       01 ARRAY.
          03 ELEMENT     PIC 9(9) OCCURS 1000000.
       01 LOW            PIC 9(9).
       01 HIGH           PIC 9(9).

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *