Patent
1994-01-04
1996-07-09
Black, Thomas G.
G06F 708
Patent
active
055353789
ABSTRACT:
The improved Quicksort method of the present invention utilizes two pointers initialized at opposite ends of the array or partition to be sorted and an initial partition value Pvalue located at the center of the array or partition. The value at each of the end pointers is then compared to Pvalue. Sorting is accomplished by recursing the partition process for the two array segments bounded on one side by the final P valve location. This method prevents excessive recursions, and allows the identical array case to recurse to the ideal minimum: Log2(N). Also, by relaxing the offsider criteria to include elements equal to Pvalue, the present invention presents arrays of two valves or a very small range of valves from recursing excessively. Further, the sorting method of the present invention may test the final position of the initial Pvalue to determine whether it is in the center (75%-95%) portion of the array or subarray being positioned. If it is not, the first Pvalue is disregarded, and a new initial Pvalue is selected, preferably randomly selected from the larger subarray bounded on one side by the final Pvalue location resulting from the initial attempt. This method prevents arrays situated in "pipe organ" sequence from recursing excessively. In addition, a maximum recursion depth limit may be specified to force section of a new initial Pvalue if a recursion level exceeds the depth limit.
REFERENCES:
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4809158 (1989-02-01), McCauley
patent: 4845744 (1989-07-01), DeBenedictic
R. Sedgewick, Algorithms, Addison-Wesley Pub. pp. 103-113, 1983.
C. Davidson, "Quicksort Revisited" IEEE Trans Software Engr. vol. 14, NO. 10, pp. 1480-1481, Oct. 1988.
V. Estivill-Castro et al. "An Adaptive Generic Sorting Algorithm that uses Variable Partitioning" Proc. IEEE 1993 Int'l Conf. Computing & Information, pp. 8-12, 1993.
Communications of the ACM, Appendix A-Benchmarks By Rudolph Loser, Mar., 1974, vol. 17, No. 3.
Unix Review, "Software Exploratorium", John Bentley, Aug., 1992 (p. 71 only).
Communications of the ACM, "Some Performance Tests of quicksort and Descendants," Rudolf Loeser, Mar. 1974, vol. 17, No. 3.
Communications of the ACM "A Class of Sorting Algorithms Based on Quicksort", Roger L. Wainwright, Apr., 1985, vol. 28, No. 4.
Communications of the ACM, "Increasing the Efficiency of Quicksort", M. H. van Emden, vol. 13, No. 9, Sep., 1970.
IEEE Transactions on Software Engineering, "Improving Quicksort Performance with a Codeword Data Structure," Jean-Loup Baer and Yi-Bing Lin, vol. 15, No. 5, May 1989.
Communications of the ACM, "Implementing Quicksort Programs", Robert Sedgewick, Oct., 1978, vol. 21, No. 10.
Black Thomas G.
Overhauser Paul B.
Wang Peter Y.
LandOfFree
Balanced and stabilized quicksort method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Balanced and stabilized quicksort method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced and stabilized quicksort method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1876233