IDENTIFICATION DIVISION. PROGRAM-ID. INTROSORT. ENVIRONMENT DIVISION. CONFIGURATION SECTION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT SORTING-INPUT ASSIGN TO "D:/Sorting/Sorting_Input.txt" ORGANIZATION IS LINE SEQUENTIAL. SELECT SORTING-OUTPUT ASSIGN TO "D:/Sorting/Output_COBOL.TXT" ORGANIZATION IS LINE SEQUENTIAL. DATA DIVISION. FILE SECTION. FD SORTING-INPUT. 01 INPUT-LINE PIC X(20). FD SORTING-OUTPUT. 01 OUTPUT-LINE PIC -9(9). WORKING-STORAGE SECTION. 01 END-OF-FILE PIC X VALUE "F". 01 VALUE-COUNT PIC 9(4) VALUE 0. 01 INTROS PIC 9(5) VALUE 0. 01 INSERTS PIC 9(5) VALUE 0. 01 HEAPS PIC 9(5) VALUE 0. 01 HEAP-SIZE PIC 9(4). 01 START-INDEX PIC 9(4). 01 END-INDEX PIC 9(4). 01 MAX-DEPTH PIC 9(4) VALUE 0. 01 START-TIME. 05 START-HOURS PIC 99. 05 START-MINS PIC 99. 05 START-SECS PIC 99. 05 START-MSECS PIC 99. 01 END-TIME. 05 END-HOURS PIC 99. 05 END-MINS PIC 99. 05 END-SECS PIC 99. 05 END-MSECS PIC 99. 01 START-TOT-SECS PIC 9(5)V99. 01 END-TOT-SECS PIC 9(5)V99. 01 ELAPSED-SECS PIC 9(5)V99. 01 SCRATCH. 02 FIRSTPART PIC 9(5). 02 SECONDPART PIC 9(5). 02 FINALPART PIC 9(4). 01 THE-VALUES. 05 VALUE-ENTRY OCCURS 1000 TIMES PIC S9(9) COMP-5. 01 SAVEFILEVARS. 02 SF-INDEX PIC 9(4). 01 SIFTDOWNVARS. 02 SD-ROOT PIC 9(4). 02 SD-START PIC 9(4). 02 SD-END PIC 9(4). 02 SD-CHILD PIC 9(4). 02 SD-TEMP PIC S9(9). 01 HEAPSORTVARS. 02 HS-ROOT PIC 9(4). 02 HS-START PIC 9(4). 02 HS-END PIC 9(4). 02 HS-CHILD PIC 9(4). 02 HS-TEMPIDX PIC 9(4). 02 HS-TEMPVAL PIC S9(9). 01 INTROSORTVARS. 02 IS-START PIC 9(4). 02 IS-END PIC 9(4). 02 IS-MAX PIC 9(4). 02 IS-LENGTH PIC 9(4). 02 IS-PART PIC S9(9). 01 INTROSORT-STACK. 02 STACK-TOP PIC 9(4) VALUE 0. 02 STACK-START OCCURS 64 TIMES PIC 9(4). 02 STACK-END OCCURS 64 TIMES PIC 9(4). 02 STACK-MAX OCCURS 64 TIMES PIC 9(4). 01 INSERTIONSORTVARS. 02 IT-START PIC 9(4). 02 IT-END PIC 9(4). 02 IT-VAL PIC S9(9). 02 IT-POS PIC 9(4). 02 IT-INDEX PIC 9(4). 01 PARTITIONVARS. 02 P-START PIC 9(4). 02 P-END PIC 9(4). 02 P-LEFT PIC 9(4). 02 P-RIGHT PIC 9(4). 02 P-PIVOT PIC S9(9). 02 P-TEMPVAL PIC S9(9). 01 RECURSIVEVARS. 02 REC-START PIC 9(4). 02 REC-END PIC 9(4). 02 REC-DEPTH PIC 9(4). 02 REC-PART PIC S9(9). 01 LOG2VARS. 02 L2-NUM PIC 9(4). 02 L2-VAL PIC 9(4). PROCEDURE DIVISION. MAIN-PROCEDURE. DISPLAY "========INTROSORT COBOL=======" PERFORM READ-FILE PERFORM DO-SORT COMPUTE START-TOT-SECS = START-HOURS * 3600 + START-MINS * 60 + START-SECS + START-MSECS / 100 COMPUTE END-TOT-SECS = END-HOURS * 3600 + END-MINS * 60 + END-SECS + END-MSECS / 100 COMPUTE ELAPSED-SECS = END-TOT-SECS - START-TOT-SECS IF ELAPSED-SECS < 0 ADD 86400 TO ELAPSED-SECS END-IF PERFORM SAVE-FILE DISPLAY "==========RUN COMPLETE==========" DISPLAY "INTROSORT TOOK " ELAPSED-SECS " SECONDS." DISPLAY "================================" DISPLAY "SORT CALLED | TIMES" DISPLAY "------------+-------------------" DISPLAY "INTRO | " INTROS DISPLAY "INSERTION | " INSERTS DISPLAY "HEAP | " HEAPS DISPLAY "--------------------------------" STOP RUN. READ-FILE. DISPLAY "READING INPUT FILE..." WITH NO ADVANCING OPEN INPUT SORTING-INPUT PERFORM UNTIL END-OF-FILE = "T" READ SORTING-INPUT AT END MOVE "T" TO END-OF-FILE NOT AT END ADD 1 TO VALUE-COUNT MOVE FUNCTION NUMVAL(INPUT-LINE) TO VALUE-ENTRY(VALUE-COUNT) END-READ END-PERFORM CLOSE SORTING-INPUT DISPLAY "DONE.". SAVE-FILE. DISPLAY "SAVING OUTPUT FILE..." WITH NO ADVANCING OPEN OUTPUT SORTING-OUTPUT PERFORM VARYING SF-INDEX FROM 1 BY 1 UNTIL SF-INDEX > VALUE-COUNT MOVE VALUE-ENTRY(SF-INDEX) TO OUTPUT-LINE WRITE OUTPUT-LINE END-PERFORM CLOSE SORTING-OUTPUT DISPLAY "DONE.". SIFT-DOWN. COMPUTE SD-CHILD = SD-START + 2 * (SD-ROOT - SD-START) + 1 PERFORM UNTIL SD-CHILD >= SD-END IF SD-CHILD + 1 < SD-END AND VALUE-ENTRY(SD-CHILD) < VALUE-ENTRY(SD-CHILD + 1) ADD 1 TO SD-CHILD END-IF IF VALUE-ENTRY(SD-ROOT) >= VALUE-ENTRY(SD-CHILD) EXIT PERFORM END-IF MOVE VALUE-ENTRY(SD-ROOT) TO SD-TEMP MOVE VALUE-ENTRY(SD-CHILD) TO VALUE-ENTRY(SD-ROOT) MOVE SD-TEMP TO VALUE-ENTRY(SD-CHILD) MOVE SD-CHILD TO SD-ROOT COMPUTE SD-CHILD = SD-START + 2 * (SD-ROOT - SD-START) + 1 END-PERFORM. HEAP-SORT. ADD 1 TO HEAPS MOVE START-INDEX TO HS-START MOVE END-INDEX TO HS-END COMPUTE HS-ROOT = HS-START + (HS-END - HS-START) / 2 - 1 PERFORM UNTIL HS-ROOT < HS-START MOVE HS-ROOT TO SD-ROOT MOVE HS-START TO SD-START MOVE HS-END TO SD-END PERFORM SIFT-DOWN SUBTRACT 1 FROM HS-ROOT END-PERFORM COMPUTE HS-TEMPIDX = HS-END - 1 PERFORM UNTIL HS-TEMPIDX <= HS-START MOVE VALUE-ENTRY(HS-START) TO HS-TEMPVAL MOVE VALUE-ENTRY(HS-TEMPIDX) TO VALUE-ENTRY(HS-START) MOVE HS-TEMPVAL TO VALUE-ENTRY(HS-TEMPIDX) MOVE HS-START TO SD-ROOT MOVE HS-START TO SD-START MOVE HS-TEMPIDX TO SD-END PERFORM SIFT-DOWN SUBTRACT 1 FROM HS-TEMPIDX END-PERFORM. INSERTION-SORT. ADD 1 TO INSERTS COMPUTE IT-INDEX = IT-START+ 1 PERFORM UNTIL IT-INDEX >= IT-END MOVE VALUE-ENTRY(IT-INDEX) TO IT-VAL COMPUTE IT-POS = IT-INDEX - 1 PERFORM UNTIL IT-POS < IT-START IF VALUE-ENTRY(IT-POS) <= IT-VAL EXIT PERFORM END-IF MOVE VALUE-ENTRY(IT-POS) TO VALUE-ENTRY(IT-POS + 1) SUBTRACT 1 FROM IT-POS END-PERFORM MOVE IT-VAL TO VALUE-ENTRY(IT-POS + 1) ADD 1 TO IT-INDEX END-PERFORM. PARTITION. MOVE P-START TO P-LEFT COMPUTE P-RIGHT = P-END - 1 MOVE VALUE-ENTRY(P-START+(P-END - P-START)/2) TO P-PIVOT PERFORM UNTIL P-LEFT > P-RIGHT PERFORM UNTIL VALUE-ENTRY(P-LEFT) >= P-PIVOT ADD 1 TO P-LEFT END-PERFORM PERFORM UNTIL VALUE-ENTRY(P-RIGHT) <= P-PIVOT SUBTRACT 1 FROM P-RIGHT END-PERFORM IF P-LEFT <= P-RIGHT MOVE VALUE-ENTRY(P-LEFT) TO P-TEMPVAL MOVE VALUE-ENTRY(P-RIGHT) TO VALUE-ENTRY(P-LEFT) MOVE P-TEMPVAL TO VALUE-ENTRY(P-RIGHT) ADD 1 TO P-LEFT SUBTRACT 1 FROM P-RIGHT END-IF END-PERFORM MOVE P-LEFT TO IS-PART. INTRO-SORT. PERFORM UNTIL STACK-TOP = 0 MOVE STACK-START(STACK-TOP) TO IS-START MOVE STACK-END(STACK-TOP) TO IS-END MOVE STACK-MAX(STACK-TOP) TO IS-MAX SUBTRACT 1 FROM STACK-TOP ADD 1 TO INTROS COMPUTE IS-LENGTH = IS-END - IS-START IF IS-LENGTH > 1 IF IS-LENGTH < 16 MOVE IS-START TO IT-START MOVE IS-END TO IT-END PERFORM INSERTION-SORT ELSE IF IS-MAX <= 0 MOVE IS-START TO HS-START MOVE IS-END TO HS-END PERFORM HEAP-SORT ELSE MOVE IS-START TO P-START MOVE IS-END TO P-END PERFORM PARTITION SUBTRACT 1 FROM IS-MAX ADD 1 TO STACK-TOP MOVE IS-PART TO STACK-START(STACK-TOP) MOVE IS-END TO STACK-END(STACK-TOP) MOVE IS-MAX TO STACK-MAX(STACK-TOP) ADD 1 TO STACK-TOP MOVE IS-START TO STACK-START(STACK-TOP) MOVE IS-PART TO STACK-END(STACK-TOP) MOVE IS-MAX TO STACK-MAX(STACK-TOP) END-IF END-IF END-IF END-PERFORM. DO-SORT. DISPLAY "SORTING ELEMENTS..." WITH NO ADVANCING MOVE VALUE-COUNT TO HEAP-SIZE ACCEPT START-TIME FROM TIME MOVE 0 TO MAX-DEPTH IF HEAP-SIZE > 1 PERFORM LOG2 END-IF MOVE 1 TO START-INDEX COMPUTE END-INDEX = HEAP-SIZE + 1 MOVE 1 TO IS-START MOVE END-INDEX TO IS-END MOVE 1 TO STACK-TOP MOVE IS-START TO STACK-START(STACK-TOP) MOVE IS-END TO STACK-END(STACK-TOP) MOVE MAX-DEPTH TO STACK-MAX(STACK-TOP) PERFORM INTRO-SORT ACCEPT END-TIME FROM TIME DISPLAY "DONE.". LOG2. MOVE HEAP-SIZE TO L2-VAL MOVE 0 TO L2-NUM PERFORM UNTIL L2-VAL < 2 DIVIDE 2 INTO L2-VAL GIVING L2-VAL ADD 1 TO L2-NUM END-PERFORM COMPUTE MAX-DEPTH = L2-NUM * 2. END PROGRAM INTROSORT.