-*- make-backup-files: nil -*- * qsort identification division. program-id. qqsort. author. Lars Nordenstrom. environment division. configuration section. input-output section. file-control. select unsorted-in assign to "qsortin" line sequential. select sorted-out assign to "qsortout" line sequential. data division. file section. fd unsorted-in record contains 80 characters. 01 row pic x(80). fd sorted-out record contains 80 characters. 01 lp pic x(80). working-storage section. 01 formatted. 05 num pic z(2)9. 05 report-line. 10 report-index pic bz(4)9. 10 report-key pic bz(8)9. 10 filler pic x value ' '. 10 report-value pic x(71). 01 data-to-be-sorted. 05 qrecords occurs 10000. 10 qkey pic 9(8). 10 filler pic x. 10 qvalue pic x(71). 01 the-stack. 05 q-sp pic 9(4) value 1. 05 q-first occurs 100 pic 9(5). 05 q-last occurs 100 pic 9(5). 05 q-sp-max pic 9(5) value 0. 01 globals. 05 idx pic 9(5) comp value 0. 05 p1 pic 9(5) comp. 05 p2 pic 9(5) comp. 01 locals. 05 i pic 9(9) comp. 05 ffirst pic 9(9) comp. 05 llast pic 9(9) comp. 05 max1 pic 9(9) comp. 05 min2 pic 9(9) comp. 01 local-booleans. 05 done-in pic 9 comp value 0. 05 q pic 9 comp value 0. procedure division. perform main stop run . swap. move qrecords (p1) to qrecords (10000) move qrecords (p2) to qrecords (p1) move qrecords (10000) to qrecords (p2) . bubble. move q-last (q-sp) to llast perform varying p1 from q-first (q-sp) by 1 until p1 >= llast compute p2 = p1 compute i = p1 + 1 perform varying i from i by 1 until i > llast if qkey (i) < qkey (p2) move i to p2 end-if end-perform if p2 > p1 perform swap end-if end-perform . pivot. move q-first (q-sp) to p1 move q-last (q-sp) to p2 move 0 to max1 move 999999999 to min2 perform until p1 > p2 if p1 < p2 and qkey (p1) > qkey (p2) perform swap end-if evaluate true when qkey (p1) < max1 add +1 to p1 when qkey (p2) > min2 add -1 to p2 when p1 = p2 add +1 to p1 when other if qkey (p1) > max1 move qkey (p1) to max1 end-if if qkey (p2) < min2 move qkey (p2) to min2 end-if add +1 to p1 add -1 to p2 end-evaluate end-perform add -1 to p1 add +1 to p2 . qsort. perform pivot move q-first (q-sp) to ffirst move q-last (q-sp) to llast add -1 to q-sp if p1 > ffirst add 1 to q-sp move ffirst to q-first (q-sp) move p1 to q-last (q-sp) end-if if llast > p2 add 1 to q-sp move p2 to q-first (q-sp) move llast to q-last (q-sp) end-if compute q-sp-max = function max(q-sp, q-sp-max) . verify-result. perform varying i from 2 by 1 until i > idx if qkey (i) < qkey (i - 1) display 'unsorted: ' i ' [' qkey (i) '] [' qvalue (i) ']' end-if end-perform . sort-main. if q-last (q-sp) - q-first (q-sp) < 5 perform bubble add -1 to q-sp else perform qsort end-if . read-input. perform until done-in > 0 read unsorted-in at end move 1 to done-in not at end add 1 to idx move row to qrecords (idx) * if idx >= 100 move 1 to done-in end-if if idx + 1 >= 10000 move 1 to done-in end-if end-read end-perform . write-table. perform varying i from 1 by 1 until i > idx move i to report-index move qkey (i) to report-key move qvalue (i) to report-value write lp from report-line end-perform . main. open input unsorted-in open output sorted-out perform read-input move 1 to q-first (q-sp) move idx to q-last (q-sp) perform sort-main until q-sp = 0 perform write-table perform verify-result move q-sp-max to num display 'maximum stack depth = ' num display 'idx = ' idx close sorted-out close unsorted-in .