{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T13:28:04Z","timestamp":1762176484401},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00453-011-9490-9","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T19:40:32Z","timestamp":1295984432000},"page":"879-905","source":"Crossref","is-referenced-by-count":10,"title":["On Smoothed Analysis of\u00a0Quicksort\u00a0and\u00a0Hoare\u2019s Find"],"prefix":"10.1007","volume":"62","author":[{"given":"Mahmoud","family":"Fouz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Kufleitner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nima","family":"Zeini\u00a0Jahromi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,26]]},"reference":[{"key":"9490_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"issue":"2","key":"9490_CR2","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1137\/070683921","volume":"39","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. SIAM Journal on Computing 39(2), 766\u2013782 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"9490_CR3","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1109\/FOCS.2009.14","volume-title":"Proceedings of the 50th Annual IEEE Symp. on Foundations of Computer Science (FOCS)","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. In: Proceedings of the 50th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 405\u2013414. IEEE Computer Society, New York (2009)"},{"key":"9490_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-540-45138-9_14","volume-title":"Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"C. Banderier","year":"2003","unstructured":"Banderier, C., Beier, R., Mehlhorn, K.: Smoothed analysis of three combinatorial problems. In: Rovan, B., Vojt\u00e1s, P. (eds.) Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 2747, pp. 198\u2013207. Springer, Berlin (2003)"},{"issue":"1","key":"9490_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L. Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average case and smoothed competitive analysis of the multilevel feedback algorithm. Mathematics of Operations Research 31(1), 85\u2013108 (2006)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"9490_CR6","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R. Beier","year":"2004","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. Journal of Computer and System Sciences 69(3), 306\u2013329 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"9490_CR7","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R. Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and losers in discrete optimization. SIAM Journal on Computing 35(4), 855\u2013881 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"9490_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-540-74792-5","volume-title":"Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"R. Beier","year":"2007","unstructured":"Beier, R., R\u00f6glin, H., V\u00f6cking, B.: The smoothed number of Pareto optimal solutions in bicriteria integer optimization. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 4513, pp. 53\u201367. Springer, Berlin (2007)"},{"key":"9490_CR9","doi-asserted-by":"crossref","unstructured":"Cederman, D., Tsigas, P.: GPU-quicksort: a practical quicksort algorithm for graphics processors. ACM J. Exp. Algorithms 14 (2009)","DOI":"10.1145\/1498698.1564500"},{"key":"9490_CR10","unstructured":"Damerow, V., Manthey, B., auf\u00a0der Heide, F.M., R\u00e4cke, H., Scheideler, C., Sohler, C., Tantau, T.: Smoothed analysis of left-to-right maxima with applications. ACM Trans. Algorithms (to appear)"},{"key":"9490_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"9490_CR12","first-page":"1295","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Englert","year":"2007","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1295\u20131304. SIAM, Philadelphia (2007)"},{"issue":"3","key":"9490_CR13","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1093\/comjnl\/27.3.276","volume":"27","author":"H. Erki\u00f6","year":"1984","unstructured":"Erki\u00f6, H.: The worst case permutation for median-of-three quicksort. The Computer Journal 27(3), 276\u2013277 (1984)","journal-title":"The Computer Journal"},{"key":"9490_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-642-02882-3_17","volume-title":"Proceedings of the 15th Annual International Computing and Combinatorics Conference (COCOON)","author":"M. Fouz","year":"2009","unstructured":"Fouz, M., Kufleitner, M., Manthey, B., Zeini\u00a0Jahromi, N.: Smoothed analysis of quicksort and Hoare\u2019s find. In: Ngo, H.Q. (ed.) Proceedings of the 15th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 5609, pp. 158\u2013167. Springer, Berlin (2009)"},{"issue":"7","key":"9490_CR15","first-page":"322","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 64: Quicksort. Communications of the ACM 4(7), 322 (1961)","journal-title":"Communications of the ACM"},{"issue":"7","key":"9490_CR16","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: Find. Communications of the ACM 4(7), 321\u2013322 (1961)","journal-title":"Communications of the ACM"},{"issue":"1","key":"9490_CR17","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1017\/S0963548397003325","volume":"7","author":"P. Kirschenhofer","year":"1998","unstructured":"Kirschenhofer, P., Prodinger, H.: Comparisons in Hoare\u2019s find algorithm. Combinatorics, Probability and Computing 7(1), 111\u2013120 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"1\u20132","key":"9490_CR18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<143::AID-RSA7>3.0.CO;2-V","volume":"10","author":"P. Kirschenhofer","year":"1997","unstructured":"Kirschenhofer, P., Prodinger, H., Martinez, C.: Analysis of Hoare\u2019s find algorithm with median-of-three partition. Random Structures and Algorithms 10(1\u20132), 143\u2013156 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"9490_CR19","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, 2nd edn. The Art of Computer Programming, vol.\u00a03. Addison-Wesley, Reading (1998)","edition":"2"},{"issue":"3","key":"9490_CR20","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.tcs.2007.02.035","volume":"378","author":"B. Manthey","year":"2007","unstructured":"Manthey, B., Reischuk, R.: Smoothed analysis of binary search trees. Theoretical Computer Science 378(3), 292\u2013315 (2007)","journal-title":"Theoretical Computer Science"},{"key":"9490_CR21","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/1.9781611973068.51","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., R\u00f6glin, H.: Improved smoothed analysis of k-means clustering. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 461\u2013470. SIAM, Philadelphia (2009)"},{"key":"9490_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1007\/978-3-642-10631-6_103","volume-title":"Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC)","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., R\u00f6glin, H.: Worst-case and smoothed analysis of k-means clustering with Bregman divergences. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 5878, pp. 1024\u20131033. Springer, Berlin (2009)"},{"key":"9490_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"9490_CR24","unstructured":"Neininger, R.: Limit laws for random recursive structures and algorithms. Ph.D. thesis, Universit\u00e4t Freiburg (1999)"},{"issue":"1","key":"9490_CR25","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H. R\u00f6glin","year":"2007","unstructured":"R\u00f6glin, H., V\u00f6cking, B.: Smoothed analysis of integer programming. Mathematical Programming 110(1), 21\u201356 (2007)","journal-title":"Mathematical Programming"},{"key":"9490_CR26","unstructured":"Schmidt, D.C.: qsort.c. C standard library stdlib within glibc 2.7, available at http:\/\/ftp.gnu.org\/gnu\/glibc\/ (2007)"},{"issue":"4","key":"9490_CR27","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF00289467","volume":"7","author":"R. Sedgewick","year":"1977","unstructured":"Sedgewick, R.: The analysis of quicksort programs. Acta Informatica 7(4), 327\u2013355 (1977)","journal-title":"Acta Informatica"},{"issue":"10","key":"9490_CR28","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1145\/359619.359631","volume":"21","author":"R. Sedgewick","year":"1978","unstructured":"Sedgewick, R.: Implementing quicksort programs. Communications of the ACM 21(10), 847\u2013857 (1978)","journal-title":"Communications of the ACM"},{"issue":"3","key":"9490_CR29","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/362875.362901","volume":"12","author":"R.C. Singleton","year":"1969","unstructured":"Singleton, R.C.: Algorithm 347: an efficient algorithm for sorting with minimal storage. Communications of the ACM 12(3), 185\u2013186 (1969)","journal-title":"Communications of the ACM"},{"issue":"3","key":"9490_CR30","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM 51(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"10","key":"9490_CR31","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM 52(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-011-9490-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T03:49:54Z","timestamp":1559965794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9490-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,26]]},"references-count":31,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9490"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9490-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,26]]}}}