Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-01
2004-01-20
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C711S108000, C711S206000, C711S207000, C711S208000, C711S209000
Reexamination Certificate
active
06681224
ABSTRACT:
FIELD OF THE INVENTION
The present invention in general relates to a technology for sorting data, such as numerical values or text. More particularly, this invention relates to a technology with which the data can be sorted speedily.
BACKGROUND OF THE INVENTION
Various modes (i.e. systems, or methods) that are used when sorting data are. For example, the well-known quick sorting mode, a radic sorting mode, and a multiple division sorting mode are known conventionally. These sorting modes are not, however, universal since they have both merits and demerits depending on the quantity and properties of data to be sorted. It is, therefore, necessary to involve a person familiar with sort target data and sorting modes and having advanced knowledge in the selection of a sorting mode. From this, means and methods with which even a person who does not have advanced knowledge about sorting can appropriately execute sorting have been conventionally demanded.
As one of the sorting modes, the above-stated quick sorting mode, radic sorting mode, multiple division sorting mode and the like are conventionally employed in various fields. The quick sorting mode is to execute sorting at high speed by dividing sort target data into small groups. Description will be given to procedures for sorting sort target databy quick sorting with reference to the following terms (a-
1
) to (e-
1
).
(a-1)
5
6
3
2
8
4
7
1
*
(b-1)
(3
2
4
1)
5
(6
8
7)
*
(c-1)
(3
2
4
1)
5
(6
8
7)
*
*
(d-1)
(2
1)
3
4
5
6
(8
7)
*
*
(e-1)
1
2
3
4
5
6
7
8
First, if sort target data in a sequence shown in the term (a-
1
) are given, the forefront data or “5” (indicated by symbol *) is selected as a reference value. Next, as shown in the term (b-
1
), lower values (“3”, “2”, “4” and “1”) than the reference value “5” (indicated by symbol *) are put before the reference value “5” and higher values (“6”, “8” and “7”) than the reference value “5” are put after the reference value “5”. In this way, the term (b-
1
) is divided into unsorted two groups as indicated by brackets, i.e., a group (“3”, “2”, “4” and “1”) put before the reference value “5” and a group (“6”, “8” and “7”) put after the reference value “5”.
Next, in the term (c-
1
), “3” (indicated by symbol *) and “6” (indicated by symbol *) at the forefronts of two bracketed groups are selected as reference values, respectively. Next, as shown in the term (d-
1
), lower values (“2” and “1”) than a reference value “3” are put before the reference value “3” and a higher value (“4”) than the reference value “3” is put after the reference value “3” in one group. Higher values (“8” and “7”) than a reference value “6” are put before the reference value “6” in the other group. In the other group, no value lower than the reference value “6” exists.
As a result, the term (d-
1
) is divided into two unsorted groups, i.e. , the bracketed group (“2” and “1”) put before the reference value “3” and the bracketed group (“8” and “7”) put after the reference value “6”. Next, in the term (e-
1
), “2” (indicated by symbol *) and “8” (indicated by symbol *) at the forefronts of the two bracketed groups are set as reference values, respectively.
Next, as shown in the term (e-
1
), a lower value (“1”) than the reference value “2” is put before the reference value “2” in one group. In this case, no value higher than the reference value “2” exists. A lower value (“7”) than the reference value “8” is put before the reference value “8” in the other group. In the other group, no higher value than the reference value “8” exists. Through the above-stated quick sorting procedures, the sort target data shown in the term (a-
1
) are sorted as shown in the term (e-
1
) in ascending order.
In case of the quick sorting stated above, as sorting (the division of the sort target data) proceeds, access to a memory storing the sort target data becomes local. Due to this, the quick sorting is characterized by high sorting speed. Here, the sorting speed O
q
of the quick sorting is expressed by the following formula (1) while assuming that the number of sort target data is n:
O
q
=n·log
2
n
(1)
Further, the radic sorting stated above is a mode for dividing sort target data into figures and executing sorting for each figure. Procedures for sorting sort target data by means of radic sorting will be described next with reference to the following terms (a-
2
) to (c-
2
):
(a-2)
17 20 30 45 46
(b-2)
20 30 45 46 17
(sorted with first
figures as keys)
(c-2)
17 20 30 45 46
(sorted with second
figures as keys)
In case of executing the radic sorting, two buffers (which will be referred to as “buffer A” and “buffer B”) are used. Namely, sort target data (two-figure numerical value) in the term (a-
2
) are sorted in ascending order with first figures as keys, as shown in the term (b-
2
). The sorting result is stored in the buffer A. Next, as shown in the term (c-
2
), the sorting result stored in the buffer A is sorted in ascending order with second figures as keys. This sorting result is stored in the buffer B. In this way, the radic sorting is required to access the buffers by as much as the number of figures of the sort target data.
The sorting speed O
r
of the above-stated radic sorting is expressed by the following formula (2) while assuming that the number of the figures of the sort target data is m and the number of the sort target data is n:
O
r
=m·n
(2)
Further, the multiple division sorting is a mode devised to accelerate the sorting speed of the quick sorting stated above. In this multiple division sorting mode, sort target data are divided into segments in advance and quick sorting is executed in units of divided segments. Here, the sorting speed O
m
of the multiple division sorting is expressed by the following formula (3) while assuming that the number of segments is L and the number of the sort target data is n, and the sorting speed O
m
is expected to be higher than the sorting speed O
q
of the quick sorting expressed by the formula (1) by n/L:
O
m
=L
·(
n/L
)·
log
2
(
n/L
) (3)
Meanwhile, as described above, as sorting proceeds, access to the memory becomes local in the quick sorting. Due to this, the quick sorting has normally, advantageously high sorting speed. However, if the quantity of the sort target data is small, the sorting speed of the quick sorting becomes disadvantageously lower than the sorting speed of the radic sorting as can be seen from the formulas (1) and (2).
The radic sorting has, by contrast, advantageously high sorting speed if the number of the sort target data is small. Actually, however, in case of the radio sorting, if the capacities of buffers are insufficient relatively to the quantity of the sort target data, it is necessary to secure a sorting region in a main storage region which is accessed slow. In this case, the access time of the main storage region has an adverse effect on the sorting speed of the radic sorting, and the sorting speed becomes eventually, disadvantageously lower.
Further, in theory, the multiple division sorting can advantageously execute sorting at higher speed than that of the quick sorting if the sort target data is optimally divided into segments. Actually, however, if the sort target data is not divided into segments in consideration of data distributed conditions, segment division often fails. As a result, the segment division time is consumed for nothing, and the sorting speed becomes disadvantageously lower than that of the quick sorting.
As can be seen from the above, the quick sorting algorithm, the radic sorting algorithm and the multiple division sorting algorithm have both merits and demerits depending on the quantity and properties of sort target data and these modes are not, therefore, not universal. For that reason, if a sorting mode having high sorting speed is selected, it is necessary to involve a person familiar with sort target data and sorting modes.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a sorting device, a sortin
Coby Frantz
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Method and device for sorting data, and a computer product does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for sorting data, and a computer product, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for sorting data, and a computer product will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253364