{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,9]],"date-time":"2025-11-09T07:40:55Z","timestamp":1762674055853},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,8,18]],"date-time":"2015-08-18T00:00:00Z","timestamp":1439856000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00224-015-9633-5","type":"journal-article","created":{"date-parts":[[2015,8,17]],"date-time":"2015-08-17T02:44:26Z","timestamp":1439779466000},"page":"528-578","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Towards a Realistic Analysis of the QuickSelect Algorithm"],"prefix":"10.1007","volume":"58","author":[{"given":"Julien","family":"Cl\u00e9ment","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James Allen","family":"Fill","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thu Hien","family":"Nguyen Thi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brigitte","family":"Vall\u00e9e","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,18]]},"reference":[{"key":"9633_CR1","doi-asserted-by":"crossref","unstructured":"C\u00e9nac, P., Chauvin, B., Paccaut, F., Pouyanne, N.: Uncommon suffix tries. Random Struct. Algoritm. (2013)","DOI":"10.1002\/rsa.20500"},{"issue":"1","key":"9633_CR2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02679623","volume":"29","author":"J Cl\u00e9ment","year":"2001","unstructured":"Cl\u00e9ment, J., Flajolet, P., Vall\u00e9e, B.: Dynamical sources in information theory: a general analysis of trie structures. Algorithmica 29(1), 307\u2013369 (2001)","journal-title":"Algorithmica"},{"key":"9633_CR3","first-page":"598","volume-title":"30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"J Cl\u00e9ment","year":"2013","unstructured":"Cl\u00e9ment, J., Nguyen Thi, T. H., Vall\u00e9e, B.: A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp. 598\u2013609. Dagstuhl, Germany (2013)"},{"issue":"01","key":"9633_CR4","first-page":"104","volume":"24","author":"J Cl\u00e9ment","year":"2014","unstructured":"Cl\u00e9ment, J., Nguyen Thi, T. H., Vall\u00e9e, B.: Towards a realistic analysis of some popular sorting algorithms. Special issue of CPC (Combinatorics, Probability and Computing) dedicated to Philippe Flajolet 24(01), 104\u2013144 (2014)","journal-title":"Special issue of CPC (Combinatorics, Probability and Computing) dedicated to Philippe Flajolet"},{"key":"9633_CR5","unstructured":"De Bruijn, N.: Asymptotic methods in analysis, Dover (1981)"},{"key":"9633_CR6","doi-asserted-by":"crossref","unstructured":"Fill, J., Matterer, J.: QuickSelect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case Find. To appear in the special issue of CPC dedicated to Philippe Flajolet (2014)","DOI":"10.1017\/S0963548314000121"},{"issue":"3","key":"9633_CR7","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1007\/s00453-009-9294-3","volume":"58","author":"JA Fill","year":"2010","unstructured":"Fill, J.A., Nakama, T.: Analysis of the expected number of bit comparisons required by QuickSelect. Algorithmica 58(3), 730\u2013769 (2010)","journal-title":"Algorithmica"},{"key":"9633_CR8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1017\/S000186780000639X","volume":"45","author":"JA Fill","year":"2013","unstructured":"Fill, J.A., Nakama, T.: Distributional convergence for the number of symbol comparisons used by QuickSelect. Adv. Appl. Probab. 45, 425\u2013450 (2013)","journal-title":"Adv. Appl. Probab."},{"issue":"1&2","key":"9633_CR9","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0304-3975(94)00281-M","volume":"144","author":"P Flajolet","year":"1995","unstructured":"Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and Rice\u2019s integrals. Theor. Comput. Sci. 144(1&2), 101\u2013124 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9633_CR10","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic combinatorics. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511801655"},{"issue":"4","key":"9633_CR11","doi-asserted-by":"crossref","first-page":"303","DOI":"10.2989\/QM.2008.31.4.1.605","volume":"31","author":"PJ Grabner","year":"2008","unstructured":"Grabner, P.J., Prodinger, H.: On a constant arising in the analysis of bit comparisons in Quickselect. Quaestiones Mathematicae 31(4), 303\u2013306 (2008)","journal-title":"Quaestiones Mathematicae"},{"issue":"7","key":"9633_CR12","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 63: partition. Commun. ACM 4(7), 321 (1961)","journal-title":"Commun. ACM"},{"issue":"7","key":"9633_CR13","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 64: Quicksort. Commun. ACM 4(7), 321 (1961)","journal-title":"Commun. ACM"},{"issue":"1","key":"9633_CR14","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"CAR Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10\u201315 (1962)","journal-title":"Comput. J."},{"key":"9633_CR15","unstructured":"Knuth, D.E.: Mathematical analysis of algorithms. In: IFIP Congress (1), pp 19\u201327 (1971)"},{"key":"9633_CR16","volume-title":"The art of computer programming, vol 3, 2nd edn. Sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The art of computer programming, vol 3, 2nd edn. Sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City (1998)"},{"issue":"4","key":"9633_CR17","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1214\/aoms\/1177730881","volume":"17","author":"F Mosteller","year":"1946","unstructured":"Mosteller, F.: On some useful inefficient statistics. Ann. Math. Statist. 17(4), 377\u2013408 (1946)","journal-title":"Ann. Math. Statist."},{"key":"9633_CR18","unstructured":"Nguyen Thi, T. H.: Towards a realistic analysis of sorting and searching algorithms. PhD thesis, Universit\u00e9 de Caen Basse Normandie (2014)"},{"key":"9633_CR19","unstructured":"N\u00f6rlund, N.E.: Le\u00e7ons sur les \u00e9quations lin\u00e9aires aux diff\u00e9rences finies. Collection de monographies sur la th\u00e9orie des fonctions, p 1929. Gauthier-Villars, Paris"},{"key":"9633_CR20","volume-title":"Vorlesungen \u00fcber Differenzenrechnung","author":"NE N\u00f6rlund","year":"1954","unstructured":"N\u00f6rlund, N.E.: Vorlesungen \u00fcber Differenzenrechnung. Chelsea Publishing Company, New York (1954)"},{"key":"9633_CR21","volume-title":"Quicksort. Outstanding dissertations in the computer sciences","author":"R Sedgewick","year":"1975","unstructured":"Sedgewick, R.: Quicksort. Outstanding dissertations in the computer sciences. Garland Publishing, New York (1975)"},{"key":"9633_CR22","volume-title":"Quicksort","author":"R Sedgewick","year":"1980","unstructured":"Sedgewick, R.: Quicksort. Garland Pub. Co., New York (1980)"},{"key":"9633_CR23","unstructured":"Sedgewick, R., Flajolet, P.: An introduction to the analysis of algorithms. Addison-Wesley-Longman (1996)"},{"key":"9633_CR24","doi-asserted-by":"crossref","unstructured":"Seidel, R.: Data-specific analysis of string sorting. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, SODA, pp. 1278\u20131286 (2010)","DOI":"10.1137\/1.9781611973075.102"},{"issue":"1\/2","key":"9633_CR25","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/BF02679622","volume":"29","author":"B Vall\u00e9e","year":"2001","unstructured":"Vall\u00e9e, B.: Dynamical sources in information theory: fundamental intervals and word prefixes. Algorithmica 29(1\/2), 262\u2013306 (2001)","journal-title":"Algorithmica"},{"key":"9633_CR26","doi-asserted-by":"crossref","unstructured":"Vall\u00e9e, B., Cl\u00e9ment, J., Fill, J.A., Flajolet, P.: The number of symbol comparisons in QuickSort and QuickSelect. In: Albers, S., et al. (eds.) Proceedings of ICALP 2009, Part I, vol. 5555 of Lecture Notes in Computer Science, pp. 750\u2013763. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_62"},{"issue":"9","key":"9633_CR27","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/362736.362753","volume":"13","author":"MH van Emden","year":"1970","unstructured":"van Emden, M.H.: Increasing the efficiency of quicksort. Commun. ACM 13(9), 563\u2013567 (1970)","journal-title":"Commun. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9633-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9633-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9633-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T12:10:48Z","timestamp":1567080648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9633-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,18]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["9633"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9633-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,18]]}}}