| 摘要 |
1277852 Sorting INTERNATIONAL BUSINESS MACHINES CORP 13 Nov 1970 [24 Dec 1969] 54029/70 Heading G4M The sorted sequence of items to be sorted is represented by the sequence of indices associated with their addresses. Variable-length stored records each include a key. The addresses of the records are entered in the unsorted order into an address table, and in each case the index position of the address entry in the table is placed in its correct position in an index table which stores the indices in the sorted order of the corresponding keys as follows. Each new index is placed at the top of the occupied part of the index table (which is filled from the bottom up and the existing entries of which are in the sorted order of the corresponding keys), a binary search being done in the index table to find the proper insertion position for the new index by comparing its corresponding key with those corresponding to the index table entries (keys accessed using the address table, of course). The index table entries above the proper insertion position are moved up to make room and the new index is inserted. When the index table is full, its top entry and the corresponding entry in the address table are removed, and the latter address (or the record) is output as part of the sorted sequence. When end of (unsorted) file is reached, the remaining addresses (or records) are output in the sorted order specified by the index table. A sequential search or a quadratic search may replace the binary search.
|
