JP3534471B2 - Merge sort method and merge sort device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to improvements in a merge sort method and merge sort device. When the database is created, the data is sorted in ascending or descending order, or when new data is added to the database and it becomes necessary to sort the data, the data is sorted. .

As one of the sorting methods, a merge sort method is widely adopted in which each data in a data string is alternately distributed and then sorted and merged (merged), but when the data amount is large. Sorting takes time.

In recent years, even in terminal devices, there is a demand for shortening the data search time for business processing, so the frequency of sort processing is increasing, and there is a demand for speeding up sort processing.

[0004]

2. Description of the Related Art FIG. 8 is an explanatory view of a conventional merge sort method. FIG. 8 shows an example of the merge sort method. For example, when 8 pieces of data having record numbers 0 to 7 are rearranged in the order of data size (ascending order), first, record number 0 After allocating the data and the data of record NO = 1, they are merged. At the time of this merge, it is arranged in the order of the size of the data. As a result, the data string shown in is obtained.

Subsequently, when the data of record No. = 2 and the data of record No. = 3 are sorted and merged,
The data string of is obtained. In this way, a data string in which two sets of data are sorted is obtained.

In the next step, a data string is obtained by merging a data string and a data string. Similarly, a data string is obtained from a data string, and a data string is obtained by merging with this data string. To be This data string becomes the target data string sorted in ascending order.

The processing for merging is as follows, taking a data string and a data string as an example.
First, the head (0002) of the data string and the head (0001) of the data string are compared. Since (0001) is smaller, this data is stored in the buffer. Next, the data string (0002) is compared with the data string (0006). (0002) is smaller, so (0002)
Is stored next to (0001) in the buffer. Next, the data string (0005) is compared with the data string (0006). (0005) is smaller, so (0005)
Is stored next to (0002) in the buffer. Here, since there is no remaining comparison data, (0006) is stored at the end.

As described above, by repeating the procedure of merging two sets of data strings for each of the arranged sequences, one data sequence arranged in ascending order can be obtained.

[0009]

The database is often searched for in business processing in the terminal device, but if the database is not sorted in a predetermined order such as ascending order or descending order, it takes time to search. Therefore, when the amount of unsorted data reaches a certain amount due to the addition of data or the like, the sorting process is normally performed automatically, and the operator is kept waiting during that time.

The above-described merge sort method or the like is adopted for this sort processing, but in recent years the amount of data has increased due to the increase in the capacity of the hard disk, and the sort processing requires more and more time.

In view of the above problems, it is an object of the present invention to provide a merge sort method that shortens the sort time.

[0012]

In order to solve the above-mentioned problems, the merge sort method of the present invention, as shown in the principle diagram of FIG. 1 of the present invention, is as follows: (1) A data string to be sorted is searched and a sorting process is performed. Unnecessary subsets are extracted, and a predetermined merge process is performed to merge the subsets as a sorted list to sort the data strings. (2) As a merge sort processing device that realizes (1) above,
It is configured to include a sort unnecessary portion extraction processing unit that searches a data string to be sorted and extracts a subset that does not require sorting, and a merge processing unit that performs a predetermined merge process based on the subset.

[0013]

[Action]

(1) First, a series of data strings that do not require a sorting process are extracted as a subset (sort unnecessary part) from the data string to be sorted. A predetermined merge process for sorting and merging the subsets as the first sorted list is performed.

In general, when sorting is performed, there are many sorted data strings. Therefore, when the merge sort is performed starting from this set, the sort time is significantly shortened. At this time, the size of each subset does not have to be constant. (2) In the device that realizes (1) above, the sort unnecessary part extraction processing unit extracts a series of data that does not require sort processing from the data string to be sorted as a subset, and the merge processing unit uses this subset as a reference. As a predetermined merge process is performed.

As described above, if the sort-unnecessary subset is large, the first few steps of merge processing can be omitted and the sort processing speed can be greatly reduced, as compared with the conventional example.

[0016]

FIG. 2 is a block diagram of one embodiment, FIG. 3 is a flowchart of basic operation, FIG. 4 is a flowchart of sort unnecessary portion extraction processing, FIG. 5 is a diagram showing sort unnecessary portion extraction processing example, and FIG. FIG. 7 is a flowchart of sort processing, and FIG. 7 is a diagram illustrating an example of merge sort processing.

In the present embodiment, as a concrete explanation, what is applied to a data string of 8 records (a record is a unit of data) shown in FIG. 8 is shown. This number of records is limited by the buffer capacity for performing the sorting process, and the process of this part is called so-called internal sorting. If the data string to be sorted is larger than this buffer capacity (8 records in this case), so-called external sorting is performed using these 8 records as a block.

FIG. 2 shows the merge sort part of the data processing device (terminal device). In FIG. 2, reference numeral 1 denotes a central processing unit CPU, which runs the following respective parts constituted by programs to control the merge sort processing of the present embodiment.

Reference numeral 2 denotes a merge sort control unit, which comprises a data read processing unit 3, a sort unnecessary portion extraction processing unit 4, a sort unnecessary portion merge processing unit 5, and a data writing processing unit 6. Here, the data read processing unit 3 sequentially reads from the file device 7 a number of data corresponding to the buffer capacity from the data string to be sorted and stores the data in the buffer 9, and the sort unnecessary part extraction processing unit 4 The data stored in the buffer 9 is searched, and the sorting process is unnecessary (here, the ascending order is used).
A continuous data sequence (sort unnecessary part) is extracted, and the first record NO of the data sequence is stored in the sort index 10. The sort unnecessary part merge processing unit 5 refers to the sort index 10 The data writing processing unit 6 replaces the data with the sorted record No. and stores it in the file device 7.

A file device 7 stores data to be sorted. A memory 8 includes a buffer 9 for performing merge sort processing, a sort index 10 described below for performing merge processing, and the like.

Here, the sort index 10 is a record in which the first record NO of the unsorted portion is stored in the order of the record NO. As will be described later, FIG. 5 shows its generation process. Hereinafter, the merge sort process is performed as follows.

[Basic Operation] See FIG. 3 (1) The data string read from the file device 7 is searched by the sort unnecessary portion extraction processing unit 4, and sort unnecessary portion extraction processing is performed. As a result, the sort index 10 that stores only the first record No of the sort unnecessary section and the number of record Nos of each sort unnecessary section are obtained. (2) The sort unnecessary section merge processing unit 5 performs the merge processing between the respective sort unnecessary sections. At this time, only the record number is sorted. (3) When the merge process is completed, the sorted records N
O is replaced with actual data and stored in the file device 7.

The detailed operation is as follows. [Sort Unnecessary Part Extraction Process] See FIG. 4, which corresponds to the basic operation (1) described above, and is performed as a preprocess of the merge process. (1) The data read processing unit 3 reads into the buffer 9 the data corresponding to the number of readable records (n). (2) Initialize the sort index 10. Here, 0 to 7 are added as the record number to the data stored in the buffer 9. (3) Compare adjacent records in order from the beginning. First,
With (m = 0), (m) and (m + 1) are compared. Here, (m) represents the content of the record NO = m. (4) If (m)> (m + 1), the record number of (m + 1) is stored in the sort index 10. This stored record number becomes the first record of the sort unnecessary part.
If (m) ≤ (m + 1), proceed to (6) below. (5) Count the number of record NOs stored in the sort index 10. (6) Repeat from (3) with m = m + 1.

From the above, the sort index 10 as shown in FIG. 5 is obtained. That is, m1 = 0 as an initial value
Is stored. Next, by comparing the data of record NO = 2 and the data of record NO = 3, it is found that the records up to record NO = 2 are sort unnecessary parts. Therefore, m1 + 1 = m2 = 3 is stored and record NO = 5. At this point, similarly, since sorting is required, m3 = 5 is stored. The number of record NOs is 3 (group A), 2 (group B), 3 (C).
Groups) are counted.

[Merge Sorting Process] Sort-necessary part In the process of the merge processor 5, the above-mentioned basic operation (1) is a merge between sort-unnecessary parts. At this time, the sort index 10 and the number of record NOs described above are used. The sort indexes 10 are merged every time merge processing is performed, and the number of sort indexes becomes 1 at the end.

As shown in FIG. 3, first, the number of sort indexes is searched. In this example, as shown in FIG. 5, since there are m1, m2, and m3 at the beginning, the number of sort indexes is 3, so the merge process is performed. If the value is 1, it means that all are aligned, and the merge process is terminated.

If the number of sort indexes> 1, two data groups are taken out from the beginning of the sort index 10 (A and B, C and D in FIG. 1, A and B and C in FIG. 5),
Each merge process is performed.

A merge process example will be described below for one set (group A, group B). See FIG. 6 and FIG. 7 (1) With reference to the sort index 10, record NOs are taken out one by one from the heads of the two data groups A and B. (2) Actual data (A) corresponding to the record No.,
(B) is extracted from the buffer 9. (3) The extracted actual data are compared, and if (A) ≧ (B), (B) is stored in the output buffer provided in the buffer 9. (4) On the other hand, if (A) <(B), (A) is stored in the output buffer, and then (B) is compared with the next (A).

When the above (3) and (4) are repeated and there is no more data to be compared, the data on the remaining side are sequentially stored in the output buffer, and the process ends. As a result, the record numbers of the A group and the B group are merged, and the sort index 10 is updated. By this update, the sort index 10 in which A and B are merged is generated. At the same time, the corresponding record number is updated.

As described above, the merging process is performed for each of the first two sets, and then the merging process is performed for each of the two sets of merged data. As a result, finally sorted record numbers are obtained in the output buffer, so that the record numbers are replaced with actual data and stored in the file device 7.

The above will be described with reference to FIG. 7 as follows. The first is the comparison between the A group and the B group, and the comparison in step 1 is performed. Therefore, first, with reference to the sort index 10, the record NO = 0 and the record NO = 3 are taken out as the first record NO of the A group and the B group.
Since (A) = 0002 and (B) = 0001,
(A) ≧ (B), and the record No. = 3 in (B) is stored in the output buffer.

Subsequently, the comparison in step 1 is performed.
As (B), the data (0007) of the next record NO is extracted from the B group and compared with (A) = (0002). The record NO = 0 of the result (A) is stored in the output buffer.

In this way, the comparison is performed, and (0007) remains at the end, so this record number is stored in the output buffer. Then, the number of sort indexes 10 becomes 2, and the configuration shown in FIG. 7 is obtained.

When the merging of the groups A and B is completed, the merging process of (A + B) and C is performed as step 2 in the same manner as described above. Then, since the number of sort indexes 10 becomes 1, the merge ends.

As described above, the data string to be sorted is searched, the unnecessary sorting portion is extracted, and the merging is started from this unnecessary portion, whereby the merging process from the data unit can be omitted. As a result, the sort-unnecessary portion is usually large, so that the merge sort process is significantly speeded up.

It should be noted that the above merge processing method is only an example and can be applied to other merge processing methods.

[0037]

As described above, according to the present invention, first,
Since a series of data strings that do not require sorting processing are extracted by searching the data strings to be sorted and the merge process is started with this data string as a subset, the conventional method of performing the merge process from the smallest data unit Compared with this, the number of merge processes can be greatly omitted, and the effect of improving the processing speed is extremely large.

[Brief description of drawings]

FIG. 1 is a principle diagram of the present invention.

FIG. 2 is a configuration diagram of an embodiment.

[Figure 3] Basic operation flowchart

FIG. 4 is a flowchart of sort unnecessary portion extraction processing.

FIG. 5 is a diagram showing an example of sort unnecessary portion extraction processing.

FIG. 6 is a flowchart of merge sort processing.

FIG. 7 is a diagram showing an example of merge sort processing.

FIG. 8 is an explanatory diagram of a conventional merge sort method.

[Explanation of symbols]

1 central processing unit CPU 2 merge sort control unit 3 data read processing unit 4 sort unnecessary section extraction processing unit 5 sort unnecessary section merge processing unit 6 data writing processing unit 7 file device 8 memory 9 buffer 10 sort index

─────────────────────────────────────────────────── --- Continuation of the front page (56) References JP-A-2-206830 (JP, A) JP-A-4-354019 (JP, A) JP-A-5-165604 (JP, A) JP-A-6- 103028 (JP, A) (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 7/24 G06F 7/32 G06F 17/30

Claims (2)

(57) [Claims] 1. Sorting a data string to be sorted by extracting a subset that does not require sorting processing and performing a predetermined merge process that merges this subset as a sorted list to sort the data string. Characteristic merge sort method. 2. An unneeded portion extraction processing unit that retrieves a data string to be sorted and extracts a subset that does not require sorting processing; and a merge processing unit that performs a predetermined merging process based on the subset. A merge sort processing device characterized by: