{"entities":{"Q2837754":{"pageid":2848478,"ns":120,"title":"Item:Q2837754","lastrevid":58037718,"modified":"2026-04-03T13:36:18Z","type":"item","id":"Q2837754","labels":{"en":{"language":"en","value":"Distributional convergence for the number of symbol comparisons used by QuickSelect"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6186887"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$6EDA9612-A1EE-4292-9700-905DC5823FBD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5ccc0d5098bd2aec53e9a966b492b27d702080f","datavalue":{"value":"1278.68354","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$3C6F8781-B238-4594-BDDB-A2F79B4F1FB8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4465d5fbabff27598012f9ef06d5a6dea50bf62b","datavalue":{"value":{"entity-type":"item","numeric-id":187944,"id":"Q187944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$2D89AE93-9FEF-4B23-81CC-ED1EBFF08C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a38beb9f0392ad57780a0a52e1e709cedb060116","datavalue":{"value":{"entity-type":"item","numeric-id":419864,"id":"Q419864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$8DA7DB7C-A403-46B8-A995-D4A2422CA123","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a18a232a5ba805729e3a0fdc88e7b61b975c21b6","datavalue":{"value":{"entity-type":"item","numeric-id":102034,"id":"Q102034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$CFF97BDC-A1C9-488B-9FEA-DA2DA2D1B276","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"047d86768cd722adf7361cd32b1edc0a73808dc4","datavalue":{"value":{"time":"+2013-07-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2837754$C62E26F6-5427-4DFD-BD4D-180F27F56CD7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66a35f8ef9cc6774537987dc81c98e80ada2f046","datavalue":{"value":"https://arxiv.org/abs/1202.2599","type":"string"},"datatype":"url"},"type":"statement","id":"Q2837754$E6FA9618-2127-4D89-9EA3-3A7587EF2A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e11e4317fb6edfe103b702fdbaddfd7b9c1e4941","datavalue":{"value":"https://projecteuclid.org/euclid.aap/1370870125","type":"string"},"datatype":"url"},"type":"statement","id":"Q2837754$A92DC7B6-89BE-4ECC-9B4B-D2365D0D5B9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$AE000680-0398-4468-8F5D-76ED7E6FCC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$961E68EB-4E08-4EB0-A97D-C901A1411616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7a6168b3aa2de4e5d12e47fa226611ee76c75fd7","datavalue":{"value":"60F25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$A5A7B92A-8805-447C-8DA0-CFC24B25F42D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a80600db4ec662d7a30e8cad3c3ab42659c31417","datavalue":{"value":"6186887","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$425D5F5E-F023-49BF-BBBA-6DDEB1D8CBBA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e033cb4d6a98de234831640e95b18126785313a9","datavalue":{"value":"QuickSelect","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$9877EC54-CFB8-4D76-A531-40878B5B530B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c531ad2c24e495ecdb6ef50b082373cd1fbf920d","datavalue":{"value":"QuickQuant","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$5BC758A8-2E57-4EFF-99FF-CB06F1265DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ff7d05c7292076bf2fa9445617e8a93bd0320d5","datavalue":{"value":"QuickVal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$79D229CB-90C2-4448-AC27-16CCDB095836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82c07e8eb345bda7453511e47998adb03c85d0b6","datavalue":{"value":"limit distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$7F2021C0-6BCD-4016-9FC0-0E6A5BEB0745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2a03b9793e735cd7570e6e196006a30a710955a","datavalue":{"value":"almost-sure convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$54A4440A-849D-4973-9548-2B80B0974529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8126d174a4f5813d2456294ef39e8e112b70611a","datavalue":{"value":"L\\(^p\\)-convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$5490F251-94AC-4B32-8770-6F00B0C9D728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2749a6830a2f02de2cc7e73c12caeb1a87b81322","datavalue":{"value":"symbol comparison","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$F9EEBAEC-2470-44E6-ADE4-33C7C347D362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9744c805929a45e6d4024bf8054a57c000058517","datavalue":{"value":"probabilistic source","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$9DE33107-B76E-412C-BAC2-D3A1A45AE37E","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"9aadc3562b5d3cd99740f94e9d46e7f210998eaf","datavalue":{"value":{"entity-type":"item","numeric-id":33419,"id":"Q33419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$2AC85F57-9F0D-4DF4-AE8F-AFE744C007E0","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$DFF479A2-2505-4BEE-891A-24B03D25FCF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51f76e65182678436c7aa33c0c0a0319d6bbe7ce","datavalue":{"value":"W3104914883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$F87DDC6D-E4A0-422D-B906-AE616DE55D60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c26807c2efabfe4028eec4255a13eb24be3d6d8","datavalue":{"value":{"entity-type":"item","numeric-id":4836494,"id":"Q4836494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$253AC860-94B3-4C67-915F-82964BF35893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1d810100e471479fafff2cc14169588cde86f8a","datavalue":{"value":{"entity-type":"item","numeric-id":1840518,"id":"Q1840518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$0E63D930-F1DD-4DA6-A2F0-835DC349E218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45f07d3a3eb135f64fedbe8d129af69479437a49","datavalue":{"value":{"entity-type":"item","numeric-id":760796,"id":"Q760796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$7F7A31D5-7828-48D8-BF7D-B9DED9E9050C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b1367bf80a5f3116681dcaba2432c6f9f6f23a","datavalue":{"value":{"entity-type":"item","numeric-id":5953102,"id":"Q5953102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$D8AF1700-FC9D-481B-9280-B83A5825A72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917ec2afa85684e3e49607fbb5f0c3bf37116839","datavalue":{"value":{"entity-type":"item","numeric-id":1950265,"id":"Q1950265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$79E45209-5775-4E83-BB79-4E9B707DC252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa00a35ed5d494d69ae32035d29d05ef81bac0a2","datavalue":{"value":{"entity-type":"item","numeric-id":428664,"id":"Q428664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$73427CED-2C38-49A8-9766-1E9D5A33EF44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4f03702c52be03337965629337336fdef1297b","datavalue":{"value":{"entity-type":"item","numeric-id":4393823,"id":"Q4393823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$1519BB3E-CC1A-4770-9CEA-617C428CD1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bf1e69110afb7b177bd30f2094c539fc76c1ff9","datavalue":{"value":{"entity-type":"item","numeric-id":4877468,"id":"Q4877468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$EE67B4A4-3053-4FA4-A894-CDEBB8B5393E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f062c73bdd8146f07f4215d613b49b5bae2f0b10","datavalue":{"value":{"entity-type":"item","numeric-id":3146984,"id":"Q3146984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$3602D7A9-1664-42B7-AB0F-D13EADF88B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4e47bc83181b603338ec2d92d5331aad8db951","datavalue":{"value":{"entity-type":"item","numeric-id":5671622,"id":"Q5671622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$688F7B67-0053-4E57-9B89-0B8FA7C4106D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12b4cad3892d24d6c789d578198f448975cc856","datavalue":{"value":{"entity-type":"item","numeric-id":1922133,"id":"Q1922133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$2282A35E-773B-404F-B204-0072C3E6B344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8da046de6c6914c28a8d44f1f438f94d2194dda","datavalue":{"value":{"entity-type":"item","numeric-id":1277384,"id":"Q1277384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$FB08BECC-4447-4320-B162-B0B8B310D209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa62e8607da3919c15c1736f4b549dee276e8b8c","datavalue":{"value":{"entity-type":"item","numeric-id":4858843,"id":"Q4858843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$B5FFE982-5A46-4575-9524-C8C1B397F7B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"748e23f9e0ef6d116b0a04dc6ba4a62563a7e2ae","datavalue":{"value":{"entity-type":"item","numeric-id":4376527,"id":"Q4376527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$33A20572-FE2E-41A8-9769-034691780795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1defdf8ef7dc5cb8fce7a707601dfc388caaa68","datavalue":{"value":{"entity-type":"item","numeric-id":672250,"id":"Q672250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$6403A662-5D8D-4337-A064-2D9E873E4D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36c9d2452ab382d549ab2ed859f371da3765be63","datavalue":{"value":{"entity-type":"item","numeric-id":3833634,"id":"Q3833634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$659E6F3E-D45D-46FF-8329-24F01BBC00F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abcc6d1cca8f2049bd8cb744f93c6067496569ce","datavalue":{"value":{"entity-type":"item","numeric-id":5750394,"id":"Q5750394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$FE45DF73-3B77-4C6C-BC5C-BE76DCCD6E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"293a7f4ab6b957a7b561d1e63b16c4b0466b1917","datavalue":{"value":{"entity-type":"item","numeric-id":1840499,"id":"Q1840499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$40EAC7FC-A988-4C11-9EE4-FD43E23497C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609bc93b5c28523dc633bf9fbed11f1fe16d52eb","datavalue":{"value":{"entity-type":"item","numeric-id":4092698,"id":"Q4092698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$FC648E99-0F94-4B5F-ACE7-363A4A2D97EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3562195191820ab6482be5ac7a1fb707200c3339","datavalue":{"value":{"entity-type":"item","numeric-id":3638078,"id":"Q3638078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$92386B5A-A16C-47AC-9E95-E45DB97D3295","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"86e6b4213232a8a2750aff7a04a4654f0654fec9","datavalue":{"value":"10.1239/AAP/1370870125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2837754$26D3042A-C620-498A-84D0-4367CFBFCAD1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"303f5a0b80ccd05851365c1af14f29e46a02ce33","datavalue":{"value":{"text":"Distributional convergence for the number of symbol comparisons used by QuickSelect","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2837754$30D070BA-868B-4915-A22B-034B9873003B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"932e0a1a1d5d819578b53685fe6c5f6433619fc8","datavalue":{"value":"The article contains an in-depth analysis of QuickSelect, the classic algorithm (described by \\textit{C. A. R.\\ Hoare} in [``Algorithm 65: Find'', Commun. ACM 4, No. 7, 321--322 (1961; \\url{doi:10.1145/366622.366647})]) to select an element with a given rank in an unordered file of elements. It is similar to QuickSort but stops the search if the current pivot element has the desired rank and continues only in the subset of remaining elements that may have the appropriate rank (different from QuickSort that continues in both parts).NEWLINENEWLINEThe algorithm has already been subject of detailed studies and precise results are known about the number of key comparisons needed and sufficient to locate the desired element. In this article the analysis is made more intricate and detailed by taking into account the cost of key comparisons under the assumption that keys are sequences of symbols from a finite alphabet. The analysis is carried out for randomly generated keys under the assumption that the keys are generated independently and identically distributed, and using continuous distributions so that the keys can be assumed to be all distinct. Three types of random key sources are considered, namely memoryless sources, Markov sources and intermittent sources.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2837754$C65612E3-379D-4F98-ADC3-C63F00A33F3F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3723b29b482d61480b3dfbfaea5e8cf64d29809c","datavalue":{"value":{"entity-type":"item","numeric-id":592022,"id":"Q592022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2837754$212D95F0-07F2-4A96-971C-5A96F1CB71A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26017840dd51e880e254066b2d266bc39be10e72","datavalue":{"value":{"entity-type":"item","numeric-id":1950265,"id":"Q1950265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19813c502b2bf23eade71899aa45886b2ee39592","datavalue":{"value":{"amount":"+0.8680317401885986","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2837754$30C20E3C-F634-495B-A0F3-B2F83C5BEAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1ee889d58bbf362678e3b8539b3e19e9b742784","datavalue":{"value":{"entity-type":"item","numeric-id":2959907,"id":"Q2959907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"468d2cff48f3740fb1146bd7ba3f7d3f63afc58b","datavalue":{"value":{"amount":"+0.8647426962852478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2837754$AF1365BC-B5F9-406E-A7D2-8AB9B7A70162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a80e78acc4caa6d524009a80ebfc514d8efee7c1","datavalue":{"value":{"entity-type":"item","numeric-id":3191202,"id":"Q3191202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bb8789a5b90c8b6241eeb40898fdb3e06ada69b","datavalue":{"value":{"amount":"+0.8606895208358765","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2837754$61713226-2E41-4B7E-A1B7-F6C75670D863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a58414734911a55ccebc594c2a5ccc441186d0d","datavalue":{"value":{"entity-type":"item","numeric-id":290901,"id":"Q290901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86075859f69a960d19c381b97c284ae1ed3f8e5d","datavalue":{"value":{"amount":"+0.8486757278442383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2837754$3032F19D-8C63-4539-A1EC-87909B1ABF35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2837754","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2837754"}}}}}