Sorting a table in memory

COBOL has a SORT verb, and it sorts files. A table that is already in memory is sorted by the program, with a loop and a swap, unless the program writes it to a work file and asks the verb to sort that. This lesson writes the loop, because it is the one place where the mechanics of a table are visible in ten lines.

A bubble sort

The idea is a comparison of neighbours: walk the table once, exchange every pair that is out of order, and repeat until a pass makes no exchange. After the first pass the largest value is at the end, after the second the two largest, and the table is sorted when a whole pass is quiet:

IDENTIFICATION DIVISION. PROGRAM-ID. BUBBLE. DATA DIVISION. WORKING-STORAGE SECTION. 01 NUMS-T. 05 NUM-E PIC 9(3) OCCURS 6 TIMES. 01 I-F PIC 9 VALUE 0. 01 J-F PIC 9 VALUE 0. 01 TEMP-F PIC 9(3) VALUE 0. 01 SWAP-F PIC X VALUE "N". 01 PASS-N PIC 9(2) VALUE 0. PROCEDURE DIVISION. MOVE 042 TO NUM-E(1). MOVE 007 TO NUM-E(2). MOVE 031 TO NUM-E(3). MOVE 019 TO NUM-E(4). MOVE 055 TO NUM-E(5). MOVE 003 TO NUM-E(6). PERFORM SHOW-ALL. PERFORM WITH TEST AFTER UNTIL SWAP-F = "N" MOVE "N" TO SWAP-F ADD 1 TO PASS-N PERFORM VARYING I-F FROM 1 BY 1 UNTIL I-F > 5 COMPUTE J-F = I-F + 1 IF NUM-E(I-F) > NUM-E(J-F) MOVE NUM-E(I-F) TO TEMP-F MOVE NUM-E(J-F) TO NUM-E(I-F) MOVE TEMP-F TO NUM-E(J-F) MOVE "Y" TO SWAP-F END-IF END-PERFORM END-PERFORM. DISPLAY "after " PASS-N " passes:". PERFORM SHOW-ALL. STOP RUN. SHOW-ALL. DISPLAY "[" NUM-E(1) "][" NUM-E(2) "][" NUM-E(3) "]" "[" NUM-E(4) "][" NUM-E(5) "][" NUM-E(6) "]".

cobc -x -free -Wall -o bubble bubble.cob
./bubble

[042][007][031][019][055][003]
after 06 passes:
[003][007][019][031][042][055]

The passes and the flag

The loop runs with TEST AFTER because the flag starts at N: with the default test before the body the loop would end on its first check, and the first version of this program printed the unsorted table after zero passes.

The sixth pass made no exchange, which is the pass that proves the table is sorted and ends the loop. The inner loop stops at five and not at six, because it compares entry I with entry I + 1; the last comparison of a pass is between the fifth and the sixth entry.

Swapping one entry

The exchange needs three statements and a temporary field, in this order: the first value into the temporary, the second into the first, the temporary into the second. COBOL has neither a tuple assignment nor a swap function, and a program that reverses the first two statements loses a value.

A table of a thousand entries needs about half a million comparisons in the worst case, which is why a program with a large table writes it to a work file and lets SORT do the work: the verb costs a file and a sort key instead of a paragraph. The lessons on SORT with USING and GIVING use it on files, and the table stays in memory only when it is small.

Sorting a table of records

A table of records sorts the same way, and the swap becomes one group move in each direction, through a record of the same layout:

IDENTIFICATION DIVISION. PROGRAM-ID. RECSORT. DATA DIVISION. WORKING-STORAGE SECTION. 01 ROWS-T. 05 ROW-E OCCURS 4 TIMES. 10 R-ID PIC X(3). 10 R-AMT PIC 9(4). 01 TEMP-REC. 05 T-ID PIC X(3). 05 T-AMT PIC 9(4). 01 I-F PIC 9 VALUE 0. 01 J-F PIC 9 VALUE 0. 01 SWAP-F PIC X VALUE "N". 01 PASS-N PIC 9(2) VALUE 0. PROCEDURE DIVISION. MOVE "C30" TO R-ID(1). MOVE 0500 TO R-AMT(1). MOVE "A10" TO R-ID(2). MOVE 0150 TO R-AMT(2). MOVE "D40" TO R-ID(3). MOVE 0999 TO R-AMT(3). MOVE "B20" TO R-ID(4). MOVE 0025 TO R-AMT(4). PERFORM SHOW-ALL. PERFORM WITH TEST AFTER UNTIL SWAP-F = "N" MOVE "N" TO SWAP-F ADD 1 TO PASS-N PERFORM VARYING I-F FROM 1 BY 1 UNTIL I-F > 3 COMPUTE J-F = I-F + 1 IF R-AMT(I-F) > R-AMT(J-F) MOVE ROW-E(I-F) TO TEMP-REC MOVE ROW-E(J-F) TO ROW-E(I-F) MOVE TEMP-REC TO ROW-E(J-F) MOVE "Y" TO SWAP-F END-IF END-PERFORM END-PERFORM. DISPLAY "after " PASS-N " passes:". PERFORM SHOW-ALL. STOP RUN. SHOW-ALL. DISPLAY R-ID(1) " " R-AMT(1) " | " R-ID(2) " " R-AMT(2) " | " R-ID(3) " " R-AMT(3) " | " R-ID(4) " " R-AMT(4).

cobc -x -free -Wall -o recsort recsort.cob
./recsort

C30 0500 | A10 0150 | D40 0999 | B20 0025
after 04 passes:
B20 0025 | A10 0150 | C30 0500 | D40 0999

The whole row travels with its amount, because the swap moves the entry and not one field. The comparison reads R-AMT(I-F) and the moves take ROW-E(I-F): a program that swaps only the key leaves the identifiers of another row attached to the amounts, which is a defect that looks like a wrong report rather than a wrong sort.

The next part is about paragraphs and sections, which is what these loops are made of: every paragraph named here is a block the compiler places, and the scope rules of the next lesson decide what runs after it.

Exercises

  1. Fill the table with the six values in reverse order and count the passes. Why is it the worst case?
  2. Change the comparison to < and run the sort again. What order do you get?
  3. Sort the records by identifier instead of amount and print them. Which line of the comparison changes?
  4. Remove the MOVE "N" TO SWAP-F from the outer loop. What happens to the program?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What ends the outer loop of a bubble sort?

    Answer

    A pass that makes no exchange, because the table is then in order

    The flag is cleared at the start of each pass and set by any exchange, so a quiet pass ends the loop.

  2. Why does the inner loop stop one short of the last entry?

    Answer

    It compares entry I with entry I + 1

    The comparison needs a neighbour, so the last pair is (n-1, n).

  3. How many statements does a swap need?

    Answer

    Three moves through a temporary field

    Moving the second value first destroys the first, so the temporary holds it.

  4. What does a swap of two rows of a table of records move?

    Answer

    The whole entry, through a record of the same layout

    The group move carries every field, which keeps the identifiers with their amounts.

  5. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q5. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC 9(2) OCCURS 3 TIMES. 01 TMP-F PIC 9(2). PROCEDURE DIVISION. MOVE 3 TO E-F(1). MOVE 1 TO E-F(2). MOVE 2 TO E-F(3). MOVE E-F(1) TO TMP-F. MOVE E-F(2) TO E-F(1). MOVE TMP-F TO E-F(2). DISPLAY E-F(1) " " E-F(2) " " E-F(3). STOP RUN.

    Answer

    01 03 02

    The three moves exchange the first two entries and leave the third alone.

  6. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q6. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC 9(2) OCCURS 3 TIMES. 01 I-F PIC 9 VALUE 0. 01 C-F PIC 9 VALUE 0. PROCEDURE DIVISION. MOVE 5 TO E-F(1). MOVE 1 TO E-F(2). MOVE 4 TO E-F(3). PERFORM VARYING I-F FROM 1 BY 1 UNTIL I-F IS GREATER THAN 2 IF E-F(I-F) IS GREATER THAN E-F(I-F + 1) ADD 1 TO C-F END-IF END-PERFORM. DISPLAY C-F. STOP RUN.

    Answer

    1

    Only the first pair is out of order; the second is 1 and 4, which is fine.

  7. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q7. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-E OCCURS 2 TIMES. 10 E-ID PIC X(1). 10 E-N PIC 9(2). 01 TMP-R. 05 T-ID PIC X(1). 05 T-N PIC 9(2). PROCEDURE DIVISION. MOVE "A" TO E-ID(1). MOVE 50 TO E-N(1). MOVE "B" TO E-ID(2). MOVE 10 TO E-N(2). MOVE E-E(1) TO TMP-R. MOVE E-E(2) TO E-E(1). MOVE TMP-R TO E-E(2). DISPLAY E-ID(1) " " E-N(1) " " E-ID(2) " " E-N(2). STOP RUN.

    Answer

    B 10 A 50

    The group moves exchange both fields of the two rows together.

  8. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q8. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-T. 05 E-F PIC 9(2) OCCURS 4 TIMES. 01 I-F PIC 9 VALUE 0. 01 S-F PIC 9(3) VALUE 0. PROCEDURE DIVISION. MOVE 4 TO E-F(1). MOVE 3 TO E-F(2). MOVE 2 TO E-F(3). MOVE 1 TO E-F(4). PERFORM VARYING I-F FROM 1 BY 1 UNTIL I-F IS GREATER THAN 4 ADD E-F(I-F) TO S-F END-PERFORM. DISPLAY S-F. STOP RUN.

    Answer

    010

    The sum does not depend on the order, and it is ten.

  9. A table of a thousand entries is sorted with a bubble sort. Why does a program with a work file use SORT instead?

    Answer

    The verb sorts in a file, and the bubble sort needs about half a million comparisons

    The in-memory loop is quadratic, and the verb exists to avoid writing and debugging one for a large table.

  10. A sort swaps only the key field of each row. What does the report show?

    Answer

    Keys in order with the other fields of the rows they were swapped out of

    The columns of a row stop belonging to each other, which no compiler can see.

The code on this page was built with cobc (GnuCOBOL) 3.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev