000100 IDENTIFICATION DIVISION.
000200 PROGRAM-ID. COMBSORT.
000300* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
000400*  AUTHOR. JAY MOSELEY.                                         *
000500*  DATE-WRITTEN. FEBRUARY, 2001.                                *
000600*  FUNCTION. THIS IS AN IMPLEMENTATION OF THE COMB SORT         *
000700*            ALGORITHM.  THE COMBSORT IS AN EXTENDED BUBBLESORT *
000800*            WHICH IS VERY FAST, IS EASILY IMPLEMENTED, AND     *
000900*            INCURS LITTLE MEMORY OVERHEAD.                     *
001000* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
001100
001200 ENVIRONMENT DIVISION.
001300
001400     SELECT TEST-DATA
001500         ASSIGN TO "SORTDATA.TXT"
001600         ORGANIZATION IS LINE SEQUENTIAL.
001700
001800 DATA DIVISION.
001900
002000 FD  TEST-DATA
002100     DATA RECORD IS TEST-RECORD.
002200 01  TEST-RECORD.
002300     02  FILLER                  PIC X(13).
002400     02  TR-SEQUENCE             PIC 9(04).
002500     02  FILLER                  PIC X(03).
002600     02  TR-KEYFIELD             PIC X(10).
002700
002800 WORKING-STORAGE SECTION.
002900
003000 01  END-OF-DATA-INDICATOR       PIC X(01)   VALUE 'N'.
003100     88  END-OF-DATA                         VALUE 'Y'.
003200
003300 01  CURRENT-DATE-AND-TIME.
003400     02  FILLER                  PIC X(08).
003500     02  CURRENT-TIME            PIC 9(06).
003600     02  FILLER                  PIC X(05).
003700
003800 01  EDIT-NUMBER                 PIC Z,ZZ9.
003900
004000 01  EDIT-TIME                   PIC Z9/99/99.99.
004100
004200* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
004300* THE FOLLOWING DATA ITEMS ARE USED DURING THE SORT PROCESS.    *
004400* SORT-GAP, AS DEFINED, WILL HANDLE A TABLE OF 9,999 ITMES.     *
004500* SORT-I, SORT-J ARE USED AS SUBSCRIPTS.                        *
004600* SORT-SIZE IS THE NUMBER OF ELEMENTS TO BE SORTED.             *
004700* SORT-SWAP IS A HOLDING FIELD FOR EXCHANGING ITEMS AND MUST    *
004800* BE AS LARGE AS A SINGLE ELEMENT OF THE TABLE BEING SORTED.    *
004900* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
005000 01  SORT-WORK.
005100     02  SORT-GAP                PIC 9(4)V99.
005200     02  FILLER                  REDEFINES SORT-GAP.
005300         03  SORT-GAP-INTEGER    PIC 9(4).
005400         03  FILLER              PIC 99.
005500
005600     02  SORT-I                  PIC S9(4)   BINARY.
005700     02  SORT-J                  PIC S9(4)   BINARY.
005800     02  SORT-SIZE               PIC S9(4)   BINARY.
005900     02  SORT-SWAP               PIC X(14).
006000
006100     02  SORT-CHANGED            PIC X(01).
006200         88  SORT-CHANGED-ORDER              VALUE 'Y'.
006300         88  SORT-UNCHANGED-ORDER            VALUE 'N'.
006400
006500* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
006600* THE FOLLOWING TABLE CONTAINS THE ELEMENTS TO BE SORTED.       *
006700* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
006800 01  SAMPLE-DATA.
006900     02  SAMPLE-ELEMENT          OCCURS 1500 TIMES.
007000         03  SAMPLE-KEY          PIC X(10).
007100         03  SAMPLE-SEQUENCE     PIC 9(04).
007200
007300 PROCEDURE DIVISION.
007400
007500* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
007600* THE ELEMENTS TO BE SORTED ARE LOADED FROM A TEXT FILE.        *
007700* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
007800 0000-LOAD-DATA.
007900
008000     OPEN INPUT TEST-DATA.
008100
008200     MOVE +0 TO SORT-SIZE.
008300
008400     PERFORM UNTIL END-OF-DATA
008500
008600         READ TEST-DATA
008700             AT END
008800                 SET END-OF-DATA TO TRUE
008900             NOT AT END
009000                 ADD +1 TO SORT-SIZE
009100                 MOVE TR-KEYFIELD TO SAMPLE-KEY (SORT-SIZE)
009200                 MOVE TR-SEQUENCE TO SAMPLE-SEQUENCE (SORT-SIZE)
009300         END-READ
009400
009500     END-PERFORM.
009600
009700     CLOSE TEST-DATA.
009800
009900     MOVE SORT-SIZE TO EDIT-NUMBER.
010000     DISPLAY 'LOADED '
010100             EDIT-NUMBER
010200             ' RECORDS.'
010300     DISPLAY ' '.
010400     MOVE FUNCTION CURRENT-DATE TO CURRENT-DATE-AND-TIME.
010500     MOVE CURRENT-TIME TO EDIT-TIME.
010600     INSPECT EDIT-TIME CONVERTING '/' TO ':'.
010700     DISPLAY 'SORT BEGINNING AT '
010800             EDIT-TIME.
010900
011000* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
011100* THE COMB SORT ALGORITHM.                                      *
011200* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
011300 0000-SORT-DATA.
011400
011500     MOVE SORT-SIZE TO SORT-GAP.
011600
011700     PERFORM UNTIL SORT-UNCHANGED-ORDER AND SORT-GAP EQUAL 1.00
011800
011900         SET SORT-UNCHANGED-ORDER TO TRUE
012000
012100         COMPUTE SORT-GAP = SORT-GAP / 1.3
012200         EVALUATE SORT-GAP-INTEGER
012300             WHEN 0
012400                 MOVE 1.00 TO SORT-GAP
012500             WHEN 9
012600             WHEN 10
012700                 MOVE 11.00 TO SORT-GAP
012800         END-EVALUATE
012900
013000         PERFORM VARYING SORT-I
013100                 FROM +1 BY +1
013200                 UNTIL SORT-I GREATER THAN
013300                       (SORT-SIZE - SORT-GAP-INTEGER)
013400
013500             COMPUTE SORT-J = SORT-I + SORT-GAP-INTEGER
013600
013700             IF SAMPLE-KEY (SORT-I) GREATER THAN
013800                SAMPLE-KEY (SORT-J)
013900                 MOVE SAMPLE-ELEMENT (SORT-J) TO SORT-SWAP
014000                 MOVE SAMPLE-ELEMENT (SORT-I) TO
014100                      SAMPLE-ELEMENT (SORT-J)
014200                 MOVE SORT-SWAP TO SAMPLE-ELEMENT (SORT-I)
014300                 SET SORT-CHANGED-ORDER TO TRUE
014400             END-IF
014500
014600         END-PERFORM
014700
014800     END-PERFORM.
014900
015000* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
015100* DISPLAY SORTED ELEMENTS.                                      *
015200* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
015300 0000-DISPLAY-DATA.
015400     MOVE FUNCTION CURRENT-DATE TO CURRENT-DATE-AND-TIME.
015500     MOVE CURRENT-TIME TO EDIT-TIME.
015600     INSPECT EDIT-TIME CONVERTING '/' TO ':'.
015700     DISPLAY 'SORT COMPLETED AT '
015800             EDIT-TIME.
015900     DISPLAY ' '.
016000
016100     PERFORM VARYING SORT-I
016200             FROM +1 BY +1
016300             UNTIL SORT-I GREATER THAN SORT-SIZE
016400
016500         DISPLAY 'Test Record #'
016600                 SAMPLE-SEQUENCE (SORT-I)
016700                 '   '
016800                 SAMPLE-KEY (SORT-I)
016900
017000     END-PERFORM.
017100
017200     STOP RUN.
017300* - - - - - - - - - - - - - - - - - - - - -> PROGRAM EXIT POINT <
017400
017500 END PROGRAM COMBSORT.