{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T08:35:52Z","timestamp":1742632552073},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[1975,3]]},"abstract":"\n A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the\n i<\/jats:italic>\n th smallest of\n n<\/jats:italic>\n numbers is\n n<\/jats:italic>\n + min(\n i,n-i<\/jats:italic>\n ) +\n o<\/jats:italic>\n (\n n<\/jats:italic>\n ). A lower bound within 9 percent of the above formula is also derived.\n <\/jats:p>","DOI":"10.1145\/360680.360691","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:34:59Z","timestamp":1027769699000},"page":"165-172","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":189,"title":["Expected time bounds for selection"],"prefix":"10.1145","volume":"18","author":[{"given":"Robert W.","family":"Floyd","sequence":"first","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]},{"given":"Ronald L.","family":"Rivest","sequence":"additional","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[1975,3]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"crossref","unstructured":"Blum M. Flyod R. W. Pratt V. Rivest R. and Tarjan R. Time bounds for selection JCSS 7(Aug. 197.) 448-461 Blum M. Flyod R. W. Pratt V. Rivest R. and Tarjan R. Time bounds for selection JCSS 7(Aug. 197.) 448-461","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360694"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366642"},{"key":"e_1_2_1_4_2","volume-title":"Stantbrd U.","author":"Knuth Donald E","year":"1971","unstructured":"Knuth , Donald E . Mathematical analysis of algorithms. Computer Sei. Dept. Rep. STAN-CS-71-206 . Stantbrd U. , Mar. 1971 .27 pp. Knuth, Donald E. Mathematical analysis of algorithms. Computer Sei. Dept. Rep. STAN-CS-71-206. Stantbrd U., Mar. 1971.27 pp."},{"key":"e_1_2_1_5_2","volume-title":"Statistical Theory","author":"Lindgren B.W.","year":"1962","unstructured":"Lindgren , B.W. Statistical Theory . The MacMillan Co. , New York , 1962 . Lindgren, B.W. Statistical Theory. The MacMillan Co., New York, 1962."},{"key":"e_1_2_1_6_2","first-page":"69","volume-title":"Courant CompLter Science Symposium 9, Randall Rustin {Ed.} Algorithmics Press","author":"Rivest Ronald L","year":"1973","unstructured":"Rivest , Ronald L . , and Floyd , Robert W. Bounds on the expected time for median computations (extended abstract) . Courant CompLter Science Symposium 9, Randall Rustin {Ed.} Algorithmics Press , New York , 1973 , pp. 69 - 76 . Rivest, Ronald L., and Floyd, Robert W. Bounds on the expected time for median computations (extended abstract). Courant CompLter Science Symposium 9, Randall Rustin {Ed.} Algorithmics Press, New York, 1973, pp. 69-76."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363394"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/360680.360691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T23:20:00Z","timestamp":1678317600000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/360680.360691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,3]]},"references-count":7,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1975,3]]}},"alternative-id":["10.1145\/360680.360691"],"URL":"https:\/\/doi.org\/10.1145\/360680.360691","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,3]]},"assertion":[{"value":"1975-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}