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.
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 :
******************************************************************
* 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 :
******************************************************************
* 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 :
******************************************************************
* 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).