zbMATH — the first resource for mathematics

On quickselect, partial sorting and multiple Quickselect. (English) Zbl 1185.68284
Summary: We present explicit solutions of a class of recurrences related to the Quickselect algorithm. Thus, we are immediately able to solve recurrences arising at the partial sorting problem, which are contained in this class. Furthermore we show how the partial sorting problem is connected to the Multiple Quickselect algorithm and present a method for the calculation of solutions for a class of recurrences related to the Multiple Quickselect algorithm. Further an analysis of an algorithm for sorting a subarray \(A[r\cdots r+p - 1]\), given the array \(A[1\cdots n]\), is provided.

68P10 Searching and sorting
68W05 Nonnumerical algorithms
Find; Quicksort
Full Text: DOI
[1] Greene, D.H.; Knuth, D.E., Mathematics for the analysis of algorithms, (1982), Birkhäuser Boston
[2] Hoare, C.A.R., Find (algorithm 65), Communications of the ACM, 4, 321-322, (1961)
[3] Hoare, C.A.R., Quicksort, Computer journal, 5, 10-15, (1962) · Zbl 0108.13601
[4] Hwang, H.-K.; Tsai, T.-H., Quickselect and dickman function, Combinatorics, probability and computing, 11, 4, 353-371, (2002) · Zbl 1008.68044
[5] Kirschenhofer, P.; Prodinger, H., Comparisons in Hoare’s FIND algorithm, Combinatorics, probability and computing, 7, 111-120, (1998) · Zbl 0892.68021
[6] Knuth, D.E., Selected papers on analysis of algorithms, (2000), CLSI Publications · Zbl 0966.68082
[7] Knuth, D.E., The art of computer programming: fundamental algorithms, vol. 1, (1997), Addison-Wesley Reading, MA · Zbl 0191.17903
[8] Knuth, D.E., The art of computer programming: sorting and searching, vol. 3, (1998), Addison-Wesley Reading, MA · Zbl 0918.68079
[9] M. Kuba, Multiple Quickselect und die Steinerdistanz in binären Suchbäumen, Diploma thesis, Technische Universität Wien, 2004
[10] C. Martínez, Partial Quicksort, in: Proc. of the 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and the 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics, 2004, pp. 224-228
[11] Panholzer, A.; Prodinger, H., Binary search tree recursions with harmonic toll functions, Journal of computational and applied mathematics, 142, 211-225, (2002) · Zbl 1005.68116
[12] Panholzer, A.; Prodinger, H., A generating function approach for the analysis of grand averages for multiple QUICKSELECT, Random structures algorithms, 13, 189-209, (1998) · Zbl 0959.68513
[13] Prodinger, H., Multiple quickselect, Hoare’s find algorithm for several elements, Information processing letters, 56, 123-129, (1995) · Zbl 0875.68313
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.