Quickselect (82536B)
1 <!DOCTYPE html> 2 <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-zebra-design-disabled vector-feature-custom-font-size-clientpref-0 vector-feature-client-preferences-disabled vector-feature-typography-survey-disabled vector-toc-available" lang="en" dir="ltr"> 3 <head> 4 <meta charset="UTF-8"> 5 <title>Quickselect - Wikipedia</title> 6 <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-zebra-design-disabled vector-feature-custom-font-size-clientpref-0 vector-feature-client-preferences-disabled vector-feature-typography-survey-disabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""], 7 "wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"726b22ff-899e-4651-9741-b4ab61fab1f1","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Quickselect","wgTitle":"Quickselect","wgCurRevisionId":1150381074,"wgRevisionId":1150381074,"wgArticleId":2899536,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles needing additional references from August 2013","All articles needing additional references","Selection algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Quickselect","wgRelevantArticleId":2899536,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], 8 "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":6,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":9000,"wgULSCurrentAutonym":"English","wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q3927837","wgCheckUserClientHintsHeadersJsApi":["architecture","bitness","brands","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false}; 9 RLSTATE={"skins.vector.user.styles":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","skins.vector.user":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","codex-search-styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.head","mmv.bootstrap.autostart","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents", 10 "ext.navigationTiming","ext.uls.compactlinks","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> 11 <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); 12 }];});});</script> 13 <link rel="stylesheet" href="/w/load.php?lang=en&modules=codex-search-styles%7Cext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cskins.vector.icons%2Cstyles%7Cwikibase.client.init&only=styles&skin=vector-2022"> 14 <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> 15 <meta name="ResourceLoaderDynamicStyles" content=""> 16 <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> 17 <meta name="generator" content="MediaWiki 1.42.0-wmf.5"> 18 <meta name="referrer" content="origin"> 19 <meta name="referrer" content="origin-when-cross-origin"> 20 <meta name="robots" content="max-image-preview:standard"> 21 <meta name="format-detection" content="telephone=no"> 22 <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/0/04/Selecting_quickselect_frames.gif"> 23 <meta property="og:image:width" content="1200"> 24 <meta property="og:image:height" content="917"> 25 <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/0/04/Selecting_quickselect_frames.gif"> 26 <meta property="og:image:width" content="800"> 27 <meta property="og:image:height" content="611"> 28 <meta property="og:image:width" content="640"> 29 <meta property="og:image:height" content="489"> 30 <meta name="viewport" content="width=1000"> 31 <meta property="og:title" content="Quickselect - Wikipedia"> 32 <meta property="og:type" content="website"> 33 <link rel="preconnect" href="//upload.wikimedia.org"> 34 <link rel="alternate" media="only screen and (max-width: 720px)" href="//en.m.wikipedia.org/wiki/Quickselect"> 35 <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Quickselect&action=edit"> 36 <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> 37 <link rel="icon" href="/static/favicon/wikipedia.ico"> 38 <link rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Wikipedia (en)"> 39 <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> 40 <link rel="canonical" href="https://en.wikipedia.org/wiki/Quickselect"> 41 <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> 42 <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> 43 <link rel="dns-prefetch" href="//meta.wikimedia.org" /> 44 <link rel="dns-prefetch" href="//login.wikimedia.org"> 45 </head> 46 <body class="skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Quickselect rootpage-Quickselect skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> 47 <div class="vector-header-container"> 48 <header class="vector-header mw-header"> 49 <div class="vector-header-start"> 50 <nav class="vector-main-menu-landmark" aria-label="Site" role="navigation"> 51 52 <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > 53 <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > 54 <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> 55 56 <span class="vector-dropdown-label-text">Main menu</span> 57 </label> 58 <div class="vector-dropdown-content"> 59 60 61 <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> 62 63 <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> 64 <div 65 class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" 66 data-feature-name="main-menu-pinned" 67 data-pinnable-element-id="vector-main-menu" 68 data-pinned-container-id="vector-main-menu-pinned-container" 69 data-unpinned-container-id="vector-main-menu-unpinned-container" 70 > 71 <div class="vector-pinnable-header-label">Main menu</div> 72 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> 73 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> 74 </div> 75 76 77 <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > 78 <div class="vector-menu-heading"> 79 Navigation 80 </div> 81 <div class="vector-menu-content"> 82 83 <ul class="vector-menu-content-list"> 84 85 <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" title="Support us by donating to the Wikimedia Foundation"><span>Donate</span></a></li> 86 </ul> 87 88 </div> 89 </div> 90 91 92 93 <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > 94 <div class="vector-menu-heading"> 95 Contribute 96 </div> 97 <div class="vector-menu-content"> 98 99 <ul class="vector-menu-content-list"> 100 101 <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> 102 </ul> 103 104 </div> 105 </div> 106 107 108 <div class="vector-main-menu-action vector-main-menu-action-lang-alert"> 109 <div class="vector-main-menu-action-item"> 110 <div class="vector-main-menu-action-heading vector-menu-heading">Languages</div> 111 <div class="vector-main-menu-action-content vector-menu-content"> 112 <div class="mw-message-box cdx-message cdx-message--block mw-message-box-notice cdx-message--notice vector-language-sidebar-alert"><span class="cdx-message__icon"></span><div class="cdx-message__content">Language links are at the top of the page across from the title.</div></div> 113 </div> 114 </div> 115 </div> 116 117 </div> 118 119 </div> 120 121 </div> 122 </div> 123 124 </nav> 125 126 <a href="/wiki/Main_Page" class="mw-logo"> 127 <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> 128 <span class="mw-logo-container"> 129 <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> 130 <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> 131 </span> 132 </a> 133 134 </div> 135 <div class="vector-header-end"> 136 137 <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> 138 <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" id="" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> 139 140 <span>Search</span> 141 </a> 142 <div class="vector-typeahead-search-container"> 143 <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> 144 <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> 145 <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> 146 <div class="cdx-text-input cdx-text-input--has-start-icon"> 147 <input 148 class="cdx-text-input__input" 149 type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" 150 > 151 <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> 152 </div> 153 <input type="hidden" name="title" value="Special:Search"> 154 </div> 155 <button class="cdx-button cdx-search-input__end-button">Search</button> 156 </form> 157 </div> 158 </div> 159 </div> 160 161 <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools" role="navigation" > 162 <div class="vector-user-links-main"> 163 164 <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > 165 <div class="vector-menu-content"> 166 167 <ul class="vector-menu-content-list"> 168 169 170 </ul> 171 172 </div> 173 </div> 174 175 176 <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > 177 <div class="vector-menu-content"> 178 179 <ul class="vector-menu-content-list"> 180 181 182 </ul> 183 184 </div> 185 </div> 186 187 188 <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > 189 <div class="vector-menu-content"> 190 191 <ul class="vector-menu-content-list"> 192 193 194 </ul> 195 196 </div> 197 </div> 198 199 200 <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > 201 <div class="vector-menu-content"> 202 203 <ul class="vector-menu-content-list"> 204 <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Quickselect" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> 205 </li> 206 <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Quickselect" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> 207 </li> 208 209 210 </ul> 211 212 </div> 213 </div> 214 215 </div> 216 217 <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > 218 <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > 219 <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> 220 221 <span class="vector-dropdown-label-text">Personal tools</span> 222 </label> 223 <div class="vector-dropdown-content"> 224 225 226 227 <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > 228 <div class="vector-menu-content"> 229 230 <ul class="vector-menu-content-list"> 231 232 <li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Quickselect" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Quickselect" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> 233 </ul> 234 235 </div> 236 </div> 237 238 <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > 239 <div class="vector-menu-heading"> 240 Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> 241 </div> 242 <div class="vector-menu-content"> 243 244 <ul class="vector-menu-content-list"> 245 246 <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> 247 </ul> 248 249 </div> 250 </div> 251 252 253 </div> 254 </div> 255 256 </nav> 257 258 </div> 259 </header> 260 </div> 261 <div class="mw-page-container"> 262 <div class="mw-page-container-inner"> 263 <div class="vector-sitenotice-container"> 264 <div id="siteNotice"><!-- CentralNotice --></div> 265 </div> 266 267 <div class="vector-main-menu-container"> 268 <div id="mw-navigation"> 269 <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site" role="navigation"> 270 <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> 271 272 </div> 273 </nav> 274 </div> 275 </div> 276 <nav id="mw-panel-toc" role="navigation" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark vector-sticky-pinned-container"> 277 <div id="vector-toc-pinned-container" class="vector-pinned-container"> 278 <div id="vector-toc" class="vector-toc vector-pinnable-element"> 279 <div 280 class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" 281 data-feature-name="toc-pinned" 282 data-pinnable-element-id="vector-toc" 283 284 285 > 286 <h2 class="vector-pinnable-header-label">Contents</h2> 287 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> 288 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> 289 </div> 290 291 292 <ul class="vector-toc-contents" id="mw-panel-toc-list"> 293 <li id="toc-mw-content-text" 294 class="vector-toc-list-item vector-toc-level-1"> 295 <a href="#" class="vector-toc-link"> 296 <div class="vector-toc-text">(Top)</div> 297 </a> 298 </li> 299 <li id="toc-Algorithm" 300 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 301 <a class="vector-toc-link" href="#Algorithm"> 302 <div class="vector-toc-text"> 303 <span class="vector-toc-numb">1</span>Algorithm</div> 304 </a> 305 306 <ul id="toc-Algorithm-sublist" class="vector-toc-list"> 307 </ul> 308 </li> 309 <li id="toc-Time_complexity" 310 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 311 <a class="vector-toc-link" href="#Time_complexity"> 312 <div class="vector-toc-text"> 313 <span class="vector-toc-numb">2</span>Time complexity</div> 314 </a> 315 316 <ul id="toc-Time_complexity-sublist" class="vector-toc-list"> 317 </ul> 318 </li> 319 <li id="toc-Variants" 320 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 321 <a class="vector-toc-link" href="#Variants"> 322 <div class="vector-toc-text"> 323 <span class="vector-toc-numb">3</span>Variants</div> 324 </a> 325 326 <ul id="toc-Variants-sublist" class="vector-toc-list"> 327 </ul> 328 </li> 329 <li id="toc-See_also" 330 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 331 <a class="vector-toc-link" href="#See_also"> 332 <div class="vector-toc-text"> 333 <span class="vector-toc-numb">4</span>See also</div> 334 </a> 335 336 <ul id="toc-See_also-sublist" class="vector-toc-list"> 337 </ul> 338 </li> 339 <li id="toc-References" 340 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 341 <a class="vector-toc-link" href="#References"> 342 <div class="vector-toc-text"> 343 <span class="vector-toc-numb">5</span>References</div> 344 </a> 345 346 <ul id="toc-References-sublist" class="vector-toc-list"> 347 </ul> 348 </li> 349 <li id="toc-External_links" 350 class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> 351 <a class="vector-toc-link" href="#External_links"> 352 <div class="vector-toc-text"> 353 <span class="vector-toc-numb">6</span>External links</div> 354 </a> 355 356 <ul id="toc-External_links-sublist" class="vector-toc-list"> 357 </ul> 358 </li> 359 </ul> 360 </div> 361 362 </div> 363 </nav> 364 365 <div class="mw-content-container"> 366 <main id="content" class="mw-body" role="main"> 367 <header class="mw-body-header vector-page-titlebar"> 368 <nav role="navigation" aria-label="Contents" class="vector-toc-landmark"> 369 370 <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > 371 <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > 372 <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> 373 374 <span class="vector-dropdown-label-text">Toggle the table of contents</span> 375 </label> 376 <div class="vector-dropdown-content"> 377 378 379 <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> 380 </div> 381 382 </div> 383 </div> 384 385 </nav> 386 <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Quickselect</span></h1> 387 388 <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > 389 <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 9 languages" > 390 <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-9" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> 391 392 <span class="vector-dropdown-label-text">9 languages</span> 393 </label> 394 <div class="vector-dropdown-content"> 395 396 <div class="vector-menu-content"> 397 398 <ul class="vector-menu-content-list"> 399 400 <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Quickselect" title="Quickselect – German" lang="de" hreflang="de" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D9%86%D8%AA%D8%AE%D8%A7%D8%A8_%D8%B3%D8%B1%DB%8C%D8%B9" title="انتخاب سریع – Persian" lang="fa" hreflang="fa" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Quickselect" title="Quickselect – French" lang="fr" hreflang="fr" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%80%B5%EC%85%80%EB%A0%89%ED%8A%B8" title="퀵셀렉트 – Korean" lang="ko" hreflang="ko" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Quickselect" title="Quickselect – Italian" lang="it" hreflang="it" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%91%D7%97%D7%99%D7%A8%D7%94_%D7%9E%D7%94%D7%99%D7%A8%D7%94_(%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D)" title="בחירה מהירה (אלגוריתם) – Hebrew" lang="he" hreflang="he" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BB%E3%83%AC%E3%82%AF%E3%83%88" title="クイックセレクト – Japanese" lang="ja" hreflang="ja" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B8%D0%BA%D1%81%D0%B5%D0%BB%D0%B5%D0%BA%D1%82" title="Квикселект – Serbian" lang="sr" hreflang="sr" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E9%80%89%E6%8B%A9" title="快速选择 – Chinese" lang="zh" hreflang="zh" class="interlanguage-link-target"><span>中文</span></a></li> 401 </ul> 402 <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3927837#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> 403 </div> 404 405 </div> 406 </div> 407 </header> 408 <div class="vector-page-toolbar"> 409 <div class="vector-page-toolbar-container"> 410 <div id="left-navigation"> 411 <nav aria-label="Namespaces"> 412 413 <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > 414 <div class="vector-menu-content"> 415 416 <ul class="vector-menu-content-list"> 417 418 <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Quickselect" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Quickselect" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> 419 </ul> 420 421 </div> 422 </div> 423 424 425 <div id="p-variants" class="vector-dropdown emptyPortlet" > 426 <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-dropdown-checkbox " aria-label="Change language variant" > 427 <label id="p-variants-label" for="p-variants-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> 428 </label> 429 <div class="vector-dropdown-content"> 430 431 432 433 <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > 434 <div class="vector-menu-content"> 435 436 <ul class="vector-menu-content-list"> 437 438 439 </ul> 440 441 </div> 442 </div> 443 444 445 </div> 446 </div> 447 448 </nav> 449 </div> 450 <div id="right-navigation" class="vector-collapsible"> 451 <nav aria-label="Views"> 452 453 <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > 454 <div class="vector-menu-content"> 455 456 <ul class="vector-menu-content-list"> 457 458 <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Quickselect"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Quickselect&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Quickselect&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> 459 </ul> 460 461 </div> 462 </div> 463 464 </nav> 465 466 <nav class="vector-page-tools-landmark" aria-label="Page tools"> 467 468 <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > 469 <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > 470 <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> 471 </label> 472 <div class="vector-dropdown-content"> 473 474 475 <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> 476 477 <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> 478 <div 479 class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" 480 data-feature-name="page-tools-pinned" 481 data-pinnable-element-id="vector-page-tools" 482 data-pinned-container-id="vector-page-tools-pinned-container" 483 data-unpinned-container-id="vector-page-tools-unpinned-container" 484 > 485 <div class="vector-pinnable-header-label">Tools</div> 486 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> 487 <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> 488 </div> 489 490 491 <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > 492 <div class="vector-menu-heading"> 493 Actions 494 </div> 495 <div class="vector-menu-content"> 496 497 <ul class="vector-menu-content-list"> 498 499 <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Quickselect"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Quickselect&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Quickselect&action=history"><span>View history</span></a></li> 500 </ul> 501 502 </div> 503 </div> 504 505 <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > 506 <div class="vector-menu-heading"> 507 General 508 </div> 509 <div class="vector-menu-content"> 510 511 <ul class="vector-menu-content-list"> 512 513 <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Quickselect" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Quickselect" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Quickselect&oldid=1150381074" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Quickselect&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Quickselect&id=1150381074&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FQuickselect"><span>Get shortened URL</span></a></li><li id="t-wikibase" class="mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3927837" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> 514 </ul> 515 516 </div> 517 </div> 518 519 <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > 520 <div class="vector-menu-heading"> 521 Print/export 522 </div> 523 <div class="vector-menu-content"> 524 525 <ul class="vector-menu-content-list"> 526 527 <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Quickselect&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Quickselect&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> 528 </ul> 529 530 </div> 531 </div> 532 533 </div> 534 535 </div> 536 537 </div> 538 </div> 539 540 </nav> 541 </div> 542 </div> 543 </div> 544 <div class="vector-column-end"> 545 <nav class="vector-page-tools-landmark vector-sticky-pinned-container" aria-label="Page tools"> 546 <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> 547 548 </div> 549 </nav> 550 </div> 551 <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> 552 <div class="vector-body-before-content"> 553 <div class="mw-indicators"> 554 </div> 555 556 <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> 557 </div> 558 <div id="contentSub"><div id="mw-content-subtitle"></div></div> 559 560 561 <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Algorithm for the kth smallest element in an array</div> 562 <style data-mw-deduplicate="TemplateStyles:r1097763485">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Quickselect" title="Special:EditPage/Quickselect">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Quickselect%22">"Quickselect"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Quickselect%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Quickselect%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Quickselect%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Quickselect%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Quickselect%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">August 2013</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this template message</a></small>)</i></span></div></td></tr></tbody></table> 563 <style data-mw-deduplicate="TemplateStyles:r1066479718">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}body.skin-minerva .mw-parser-output .infobox-header,body.skin-minerva .mw-parser-output .infobox-subheader,body.skin-minerva .mw-parser-output .infobox-above,body.skin-minerva .mw-parser-output .infobox-title,body.skin-minerva .mw-parser-output .infobox-image,body.skin-minerva .mw-parser-output .infobox-full-data,body.skin-minerva .mw-parser-output .infobox-below{text-align:center}</style><table class="infobox"><caption class="infobox-title">Quickselect</caption><tbody><tr><td colspan="2" class="infobox-image"><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:Selecting_quickselect_frames.gif" class="mw-file-description" title="Animated visualization of the quickselect algorithm. Selecting the 22st smallest value."><img alt="Animated visualization of the quickselect algorithm. Selecting the 22st smallest value." src="//upload.wikimedia.org/wikipedia/commons/0/04/Selecting_quickselect_frames.gif" decoding="async" width="280" height="214" class="mw-file-element" data-file-width="280" data-file-height="214" /></a></span><div class="infobox-caption">Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value.</div></td></tr><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="/wiki/Selection_algorithm" title="Selection algorithm">Selection algorithm</a></td></tr><tr><th scope="row" class="infobox-label">Data structure</th><td class="infobox-data"><a href="/wiki/Array_data_structure" class="mw-redirect" title="Array data structure">Array</a></td></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="/wiki/Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}"> 564 <semantics> 565 <mrow class="MJX-TeXAtom-ORD"> 566 <mstyle displaystyle="true" scriptlevel="0"> 567 <mi>O</mi> 568 </mstyle> 569 </mrow> 570 <annotation encoding="application/x-tex">{\displaystyle O}</annotation> 571 </semantics> 572 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="O"></span>(<i>n</i><sup>2</sup>)</td></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">Best-case</a> <a href="/wiki/Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}"> 573 <semantics> 574 <mrow class="MJX-TeXAtom-ORD"> 575 <mstyle displaystyle="true" scriptlevel="0"> 576 <mi>O</mi> 577 </mstyle> 578 </mrow> 579 <annotation encoding="application/x-tex">{\displaystyle O}</annotation> 580 </semantics> 581 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="O"></span>(<i>n</i>)</td></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">Average</a> <a href="/wiki/Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}"> 582 <semantics> 583 <mrow class="MJX-TeXAtom-ORD"> 584 <mstyle displaystyle="true" scriptlevel="0"> 585 <mi>O</mi> 586 </mstyle> 587 </mrow> 588 <annotation encoding="application/x-tex">{\displaystyle O}</annotation> 589 </semantics> 590 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="O"></span>(<i>n</i>)</td></tr><tr><th scope="row" class="infobox-label">Optimal</th><td class="infobox-data">Yes</td></tr></tbody></table> 591 <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, <b>quickselect</b> is a <a href="/wiki/Selection_algorithm" title="Selection algorithm">selection algorithm</a> to find the <i>k</i>th smallest element in an unordered list, also known as the <i>k</i>th <a href="/wiki/Order_statistics" class="mw-redirect" title="Order statistics">order statistic</a>. Like the related <a href="/wiki/Quicksort" title="Quicksort">quicksort</a> sorting algorithm, it was developed by <a href="/wiki/Tony_Hoare" title="Tony Hoare">Tony Hoare</a>, and thus is also known as <b>Hoare's selection algorithm</b>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1">[1]</a></sup> Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. 592 </p><p>Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> 593 <semantics> 594 <mrow class="MJX-TeXAtom-ORD"> 595 <mstyle displaystyle="true" scriptlevel="0"> 596 <mi>O</mi> 597 <mo stretchy="false">(</mo> 598 <mi>n</mi> 599 <mi>log</mi> 600 <mo>⁡<!-- --></mo> 601 <mi>n</mi> 602 <mo stretchy="false">)</mo> 603 </mstyle> 604 </mrow> 605 <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> 606 </semantics> 607 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="O(n\log n)"></span> to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> 608 <semantics> 609 <mrow class="MJX-TeXAtom-ORD"> 610 <mstyle displaystyle="true" scriptlevel="0"> 611 <mi>O</mi> 612 <mo stretchy="false">(</mo> 613 <mi>n</mi> 614 <mo stretchy="false">)</mo> 615 </mstyle> 616 </mrow> 617 <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> 618 </semantics> 619 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="O(n)"></span>, with a worst case of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}"> 620 <semantics> 621 <mrow class="MJX-TeXAtom-ORD"> 622 <mstyle displaystyle="true" scriptlevel="0"> 623 <mi>O</mi> 624 <mo stretchy="false">(</mo> 625 <msup> 626 <mi>n</mi> 627 <mrow class="MJX-TeXAtom-ORD"> 628 <mn>2</mn> 629 </mrow> 630 </msup> 631 <mo stretchy="false">)</mo> 632 </mstyle> 633 </mrow> 634 <annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation> 635 </semantics> 636 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="O(n^{2})"></span>. 637 </p><p>As with quicksort, quickselect is generally implemented as an <a href="/wiki/In-place_algorithm" title="In-place algorithm">in-place algorithm</a>, and beyond selecting the <span class="texhtml mvar" style="font-style:italic;">k</span>th element, it also partially sorts the data. See <a href="/wiki/Selection_algorithm" title="Selection algorithm">selection algorithm</a> for further discussion of the connection with sorting. 638 </p> 639 <meta property="mw:PageProp/toc" /> 640 <h2><span class="mw-headline" id="Algorithm">Algorithm</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=1" title="Edit section: Algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 641 <p>In quicksort, there is a subprocedure called <code>partition</code> that can, in linear time, group a list (ranging from indices <code>left</code> to <code>right</code>) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element <code>list[pivotIndex]</code>: 642 </p> 643 <pre><b>function</b> partition(list, left, right, pivotIndex) <b>is</b> 644 pivotValue := list[pivotIndex] 645 swap list[pivotIndex] and list[right] <i>// Move pivot to end</i> 646 storeIndex := left 647 <b>for</b> i <b>from</b> left <b>to</b> right − 1 <b>do</b> 648 <b>if</b> list[i] < pivotValue <b>then</b> 649 swap list[storeIndex] and list[i] 650 increment storeIndex 651 swap list[right] and list[storeIndex] <i>// Move pivot to its final place</i> 652 <b>return</b> storeIndex 653 </pre> 654 <p>This is known as the <a href="/wiki/Quicksort#Lomuto_partition_scheme" title="Quicksort">Lomuto partition scheme</a>, which is simpler but less efficient than <a href="/wiki/Quicksort#Hoare_partition_scheme" title="Quicksort">Hoare's original partition scheme</a>. 655 </p><p>In quicksort, we recursively sort both branches, leading to best-case <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> 656 <semantics> 657 <mrow class="MJX-TeXAtom-ORD"> 658 <mstyle displaystyle="true" scriptlevel="0"> 659 <mi>O</mi> 660 <mo stretchy="false">(</mo> 661 <mi>n</mi> 662 <mi>log</mi> 663 <mo>⁡<!-- --></mo> 664 <mi>n</mi> 665 <mo stretchy="false">)</mo> 666 </mstyle> 667 </mrow> 668 <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> 669 </semantics> 670 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="O(n\log n)"></span> time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect: 671 </p> 672 <pre><i>// Returns the k-th smallest element of list within left..right inclusive</i> 673 <i>// (i.e. left <= k <= right).</i> 674 <b>function</b> select(list, left, right, k) <b>is</b> 675 <b>if</b> left = right <b>then</b> <i>// If the list contains only one element,</i> 676 <b>return</b> list[left] <i>// return that element</i> 677 pivotIndex  := ... <i>// select a pivotIndex between left and right,</i> 678 <i>// e.g.,</i> left + floor(rand() % (right − left + 1)) 679 pivotIndex  := partition(list, left, right, pivotIndex) 680 <i>// The pivot is in its final sorted position</i> 681 <b>if</b> k = pivotIndex <b>then</b> 682 <b>return</b> list[k] 683 <b>else if</b> k < pivotIndex <b>then</b> 684 <b>return</b> select(list, left, pivotIndex − 1, k) 685 <b>else</b> 686 <b>return</b> select(list, pivotIndex + 1, right, k) 687 </pre> 688 <hr /><p>Note the resemblance to quicksort: just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> 689 <semantics> 690 <mrow class="MJX-TeXAtom-ORD"> 691 <mstyle displaystyle="true" scriptlevel="0"> 692 <mi>O</mi> 693 <mo stretchy="false">(</mo> 694 <mi>log</mi> 695 <mo>⁡<!-- --></mo> 696 <mi>n</mi> 697 <mo stretchy="false">)</mo> 698 </mstyle> 699 </mrow> 700 <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> 701 </semantics> 702 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="O(\log n)"></span> of its <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> 703 <semantics> 704 <mrow class="MJX-TeXAtom-ORD"> 705 <mstyle displaystyle="true" scriptlevel="0"> 706 <mi>O</mi> 707 <mo stretchy="false">(</mo> 708 <mi>n</mi> 709 <mo stretchy="false">)</mo> 710 </mstyle> 711 </mrow> 712 <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> 713 </semantics> 714 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="O(n)"></span> partitions. This simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice. It is also an <a href="/wiki/In-place_algorithm" title="In-place algorithm">in-place algorithm</a>, requiring only constant memory overhead if <a href="/wiki/Tail_call" title="Tail call">tail call</a> optimization is available, or if eliminating the <a href="/wiki/Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</a> with a loop: 715 </p><pre><b>function</b> select(list, left, right, k) <b>is</b> 716 <b>loop</b> 717 <b>if</b> left = right <b>then</b> 718 <b>return</b> list[left] 719 pivotIndex := ... <i>// select pivotIndex between left and right</i> 720 pivotIndex := partition(list, left, right, pivotIndex) 721 <b>if</b> k = pivotIndex <b>then</b> 722 <b>return</b> list[k] 723 <b>else if</b> k < pivotIndex <b>then</b> 724 right := pivotIndex − 1 725 <b>else</b> 726 left := pivotIndex + 1 727 </pre> 728 <h2><span class="mw-headline" id="Time_complexity">Time complexity</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=2" title="Edit section: Time complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 729 <p>Like quicksort, quickselect has good average performance, but is sensitive to the pivot that is chosen. If good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the <a href="/wiki/Geometric_series" title="Geometric series">geometric series</a>) one sees that performance is linear, as each step is linear and the overall time is a constant times this (depending on how quickly the search set reduces). However, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2}).}"> 730 <semantics> 731 <mrow class="MJX-TeXAtom-ORD"> 732 <mstyle displaystyle="true" scriptlevel="0"> 733 <mi>O</mi> 734 <mo stretchy="false">(</mo> 735 <msup> 736 <mi>n</mi> 737 <mrow class="MJX-TeXAtom-ORD"> 738 <mn>2</mn> 739 </mrow> 740 </msup> 741 <mo stretchy="false">)</mo> 742 <mo>.</mo> 743 </mstyle> 744 </mrow> 745 <annotation encoding="application/x-tex">{\displaystyle O(n^{2}).}</annotation> 746 </semantics> 747 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6e16485faf5f5237ac4fdf56e76ac7515282114" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.678ex; height:3.176ex;" alt="{\displaystyle O(n^{2}).}"></span> This occurs for example in searching for the maximum element of a set, using the first element as the pivot, and having sorted data. However, for randomly chosen pivots, this worst case is very unlikely: the probability of using more than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Cn}"> 748 <semantics> 749 <mrow class="MJX-TeXAtom-ORD"> 750 <mstyle displaystyle="true" scriptlevel="0"> 751 <mi>C</mi> 752 <mi>n</mi> 753 </mstyle> 754 </mrow> 755 <annotation encoding="application/x-tex">{\displaystyle Cn}</annotation> 756 </semantics> 757 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7eb08676206844b06ee1ddd827013317bd52e950" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.161ex; height:2.176ex;" alt="{\displaystyle Cn}"></span> comparisons, for any sufficiently large constant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> 758 <semantics> 759 <mrow class="MJX-TeXAtom-ORD"> 760 <mstyle displaystyle="true" scriptlevel="0"> 761 <mi>C</mi> 762 </mstyle> 763 </mrow> 764 <annotation encoding="application/x-tex">{\displaystyle C}</annotation> 765 </semantics> 766 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="C"></span>, is superexponentially small as a function of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> 767 <semantics> 768 <mrow class="MJX-TeXAtom-ORD"> 769 <mstyle displaystyle="true" scriptlevel="0"> 770 <mi>C</mi> 771 </mstyle> 772 </mrow> 773 <annotation encoding="application/x-tex">{\displaystyle C}</annotation> 774 </semantics> 775 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="C"></span>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2">[2]</a></sup> 776 </p> 777 <h2><span class="mw-headline" id="Variants">Variants</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=3" title="Edit section: Variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 778 <p>The easiest solution is to choose a random pivot, which yields <a href="/wiki/Almost_certain" class="mw-redirect" title="Almost certain">almost certain</a> linear time. Deterministically, one can use median-of-3 pivot strategy (as in the quicksort), which yields linear performance on partially sorted data, as is common in the real world. However, contrived sequences can still cause worst-case complexity; <a href="/wiki/David_Musser" title="David Musser">David Musser</a> describes a "median-of-3 killer" sequence that allows an attack against that strategy, which was one motivation for his <a href="/wiki/Introselect" title="Introselect">introselect</a> algorithm. 779 </p><p>One can assure linear performance even in the worst case by using a more sophisticated pivot strategy; this is done in the <a href="/wiki/Median_of_medians" title="Median of medians">median of medians</a> algorithm. However, the overhead of computing the pivot is high, and thus this is generally not used in practice. One can combine basic quickselect with median of medians as fallback to get both fast average case performance and linear worst-case performance; this is done in <a href="/wiki/Introselect" title="Introselect">introselect</a>. 780 </p><p>Finer computations of the average time complexity yield a worst case of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n(2+2\log 2+o(1))\leq 3.4n+o(n)}"> 781 <semantics> 782 <mrow class="MJX-TeXAtom-ORD"> 783 <mstyle displaystyle="true" scriptlevel="0"> 784 <mi>n</mi> 785 <mo stretchy="false">(</mo> 786 <mn>2</mn> 787 <mo>+</mo> 788 <mn>2</mn> 789 <mi>log</mi> 790 <mo>⁡<!-- --></mo> 791 <mn>2</mn> 792 <mo>+</mo> 793 <mi>o</mi> 794 <mo stretchy="false">(</mo> 795 <mn>1</mn> 796 <mo stretchy="false">)</mo> 797 <mo stretchy="false">)</mo> 798 <mo>≤<!-- ≤ --></mo> 799 <mn>3.4</mn> 800 <mi>n</mi> 801 <mo>+</mo> 802 <mi>o</mi> 803 <mo stretchy="false">(</mo> 804 <mi>n</mi> 805 <mo stretchy="false">)</mo> 806 </mstyle> 807 </mrow> 808 <annotation encoding="application/x-tex">{\displaystyle n(2+2\log 2+o(1))\leq 3.4n+o(n)}</annotation> 809 </semantics> 810 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a08267fadce2d19b80e2d2fe4ef8a3a541c1216a" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.854ex; height:2.843ex;" alt="n(2+2\log 2+o(1))\leq 3.4n+o(n)"></span> for random pivots (in the case of the median; other <i>k</i> are faster).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3">[3]</a></sup> The constant can be improved to 3/2 by a more complicated pivot strategy, yielding the <a href="/wiki/Floyd%E2%80%93Rivest_algorithm" title="Floyd–Rivest algorithm">Floyd–Rivest algorithm</a>, which has average complexity of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1.5n+O(n^{1/2})}"> 811 <semantics> 812 <mrow class="MJX-TeXAtom-ORD"> 813 <mstyle displaystyle="true" scriptlevel="0"> 814 <mn>1.5</mn> 815 <mi>n</mi> 816 <mo>+</mo> 817 <mi>O</mi> 818 <mo stretchy="false">(</mo> 819 <msup> 820 <mi>n</mi> 821 <mrow class="MJX-TeXAtom-ORD"> 822 <mn>1</mn> 823 <mrow class="MJX-TeXAtom-ORD"> 824 <mo>/</mo> 825 </mrow> 826 <mn>2</mn> 827 </mrow> 828 </msup> 829 <mo stretchy="false">)</mo> 830 </mstyle> 831 </mrow> 832 <annotation encoding="application/x-tex">{\displaystyle 1.5n+O(n^{1/2})}</annotation> 833 </semantics> 834 </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/45eddb6b735b6f51499d879f5b00fcfe40e0c484" class="mwe-math-fallback-image-inline mw-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.882ex; height:3.343ex;" alt="1.5n+O(n^{1/2})"></span> for median, with other <i>k</i> being faster. 835 </p> 836 <h2><span class="mw-headline" id="See_also">See also</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=4" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 837 <ul><li><a href="/wiki/Floyd%E2%80%93Rivest_algorithm" title="Floyd–Rivest algorithm">Floyd–Rivest algorithm</a></li> 838 <li><a href="/wiki/Introselect" title="Introselect">Introselect</a></li> 839 <li><a href="/wiki/Median_of_medians" title="Median of medians">Median of medians</a></li></ul> 840 <h2><span class="mw-headline" id="References">References</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=5" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 841 <style data-mw-deduplicate="TemplateStyles:r1011085734">.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> 842 <div class="mw-references-wrap"><ol class="references"> 843 <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1133582631">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}</style><cite id="CITEREFHoare1961" class="citation journal cs1"><a href="/wiki/Tony_Hoare" title="Tony Hoare">Hoare, C. A. R.</a> (1961). "Algorithm 65: Find". <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Comm. ACM</a></i>. <b>4</b> (7): 321–322. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366622.366647">10.1145/366622.366647</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Comm.+ACM&rft.atitle=Algorithm+65%3A+Find&rft.volume=4&rft.issue=7&rft.pages=321-322&rft.date=1961&rft_id=info%3Adoi%2F10.1145%2F366622.366647&rft.aulast=Hoare&rft.aufirst=C.+A.+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuickselect" class="Z3988"></span></span> 844 </li> 845 <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFDevroye1984" class="citation journal cs1">Devroye, Luc (1984). <a rel="nofollow" class="external text" href="http://luc.devroye.org/devroye-selection1984.pdf">"Exponential bounds for the running time of a selection algorithm"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Computer and System Sciences</i>. <b>29</b> (1): 1–7. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2884%2990009-6">10.1016/0022-0000(84)90009-6</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0761047">0761047</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Exponential+bounds+for+the+running+time+of+a+selection+algorithm&rft.volume=29&rft.issue=1&rft.pages=1-7&rft.date=1984&rft_id=info%3Adoi%2F10.1016%2F0022-0000%2884%2990009-6&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D761047%23id-name%3DMR&rft.aulast=Devroye&rft.aufirst=Luc&rft_id=http%3A%2F%2Fluc.devroye.org%2Fdevroye-selection1984.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuickselect" class="Z3988"></span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1133582631"><cite id="CITEREFDevroye2001" class="citation journal cs1">Devroye, Luc (2001). <a rel="nofollow" class="external text" href="https://luc.devroye.org/wcfind.pdf">"On the probabilistic worst-case time of 'find'<span class="cs1-kern-right"></span>"</a> <span class="cs1-format">(PDF)</span>. <i>Algorithmica</i>. <b>31</b> (3): 291–303. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-001-0046-2">10.1007/s00453-001-0046-2</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1855252">1855252</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Algorithmica&rft.atitle=On+the+probabilistic+worst-case+time+of+%27find%27&rft.volume=31&rft.issue=3&rft.pages=291-303&rft.date=2001&rft_id=info%3Adoi%2F10.1007%2Fs00453-001-0046-2&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1855252%23id-name%3DMR&rft.aulast=Devroye&rft.aufirst=Luc&rft_id=https%3A%2F%2Fluc.devroye.org%2Fwcfind.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuickselect" class="Z3988"></span></span> 846 </li> 847 <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html">Blum-style analysis of Quickselect</a>, <a href="/wiki/David_Eppstein" title="David Eppstein">David Eppstein</a>, October 9, 2007.</span> 848 </li> 849 </ol></div></div> 850 <h2><span class="mw-headline" id="External_links">External links</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quickselect&action=edit&section=6" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></h2> 851 <ul><li>"<a rel="nofollow" class="external text" href="https://www.mathworks.com/matlabcentral/fileexchange/68947-qselect">qselect</a>", <i>Quickselect algorithm in Matlab,</i> Manolis Lourakis</li></ul> 852 <!-- 853 NewPP limit report 854 Parsed by mw1432 855 Cached time: 20231125190914 856 Cache expiry: 1814400 857 Reduced expiry: false 858 Complications: [vary‐revision‐sha1, show‐toc] 859 CPU time usage: 0.189 seconds 860 Real time usage: 0.319 seconds 861 Preprocessor visited node count: 690/1000000 862 Post‐expand include size: 20433/2097152 bytes 863 Template argument size: 1042/2097152 bytes 864 Highest expansion depth: 9/100 865 Expensive parser function count: 1/500 866 Unstrip recursion depth: 1/20 867 Unstrip post‐expand size: 13038/5000000 bytes 868 Lua time usage: 0.110/10.000 seconds 869 Lua memory usage: 4520196/52428800 bytes 870 Number of Wikibase entities loaded: 0/400 871 --> 872 <!-- 873 Transclusion expansion time report (%,ms,calls,template) 874 100.00% 220.849 1 -total 875 37.99% 83.894 1 Template:Reflist 876 32.40% 71.548 3 Template:Cite_journal 877 27.34% 60.385 1 Template:Refimprove 878 24.80% 54.775 1 Template:Ambox 879 22.19% 49.008 1 Template:Short_description 880 11.94% 26.359 2 Template:Pagetype 881 10.66% 23.537 1 Template:Infobox_Algorithm 882 9.09% 20.065 1 Template:Infobox 883 5.75% 12.708 4 Template:Main_other 884 --> 885 886 <!-- Saved in parser cache with key enwiki:pcache:idhash:2899536-0!canonical and timestamp 20231125190914 and revision id 1150381074. Rendering was triggered because: page-view 887 --> 888 </div><!--esi <esi:include src="/esitest-fa8a495983347898/content" /> --><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> 889 <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Quickselect&oldid=1150381074">https://en.wikipedia.org/w/index.php?title=Quickselect&oldid=1150381074</a>"</div></div> 890 <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Selection_algorithms" title="Category:Selection algorithms">Selection algorithms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_August_2013" title="Category:Articles needing additional references from August 2013">Articles needing additional references from August 2013</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li></ul></div></div> 891 </div> 892 </main> 893 894 </div> 895 <div class="mw-footer-container"> 896 897 <footer id="footer" class="mw-footer" role="contentinfo" > 898 <ul id="footer-info"> 899 <li id="footer-info-lastmod"> This page was last edited on 17 April 2023, at 21:14<span class="anonymous-show"> (UTC)</span>.</li> 900 <li id="footer-info-copyright">Text is available under the <a rel="license" href="//en.wikipedia.org/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License">Creative Commons Attribution-ShareAlike License 4.0</a><a rel="license" href="//en.wikipedia.org/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" style="display:none;"></a>; 901 additional terms may apply. By using this site, you agree to the <a href="//foundation.wikimedia.org/wiki/Terms_of_Use">Terms of Use</a> and <a href="//foundation.wikimedia.org/wiki/Privacy_policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a href="//www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> 902 </ul> 903 904 <ul id="footer-places"> 905 <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> 906 <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> 907 <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> 908 <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> 909 <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> 910 <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> 911 <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> 912 <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> 913 <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Quickselect&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> 914 </ul> 915 916 <ul id="footer-icons" class="noprint"> 917 <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/"><img src="/static/images/footer/wikimedia-button.png" srcset="/static/images/footer/wikimedia-button-1.5x.png 1.5x, /static/images/footer/wikimedia-button-2x.png 2x" width="88" height="31" alt="Wikimedia Foundation" loading="lazy" /></a></li> 918 <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/"><img src="/static/images/footer/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" srcset="/static/images/footer/poweredby_mediawiki_132x47.png 1.5x, /static/images/footer/poweredby_mediawiki_176x62.png 2x" width="88" height="31" loading="lazy"></a></li> 919 </ul> 920 921 </footer> 922 923 </div> 924 </div> 925 </div> 926 <div class="vector-settings" id="p-dock-bottom"> 927 <ul> 928 <li> 929 930 <button class="cdx-button cdx-button--icon-only vector-limited-width-toggle" id=""><span class="vector-icon mw-ui-icon-fullScreen mw-ui-icon-wikimedia-fullScreen"></span> 931 932 <span>Toggle limited content width</span> 933 </button> 934 </li> 935 </ul> 936 </div> 937 <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw1371","wgBackendResponseTime":141,"wgPageParseReport":{"limitreport":{"cputime":"0.189","walltime":"0.319","ppvisitednodes":{"value":690,"limit":1000000},"postexpandincludesize":{"value":20433,"limit":2097152},"templateargumentsize":{"value":1042,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":13038,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 220.849 1 -total"," 37.99% 83.894 1 Template:Reflist"," 32.40% 71.548 3 Template:Cite_journal"," 27.34% 60.385 1 Template:Refimprove"," 24.80% 54.775 1 Template:Ambox"," 22.19% 49.008 1 Template:Short_description"," 11.94% 26.359 2 Template:Pagetype"," 10.66% 23.537 1 Template:Infobox_Algorithm"," 9.09% 20.065 1 Template:Infobox"," 5.75% 12.708 4 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.110","limit":"10.000"},"limitreport-memusage":{"value":4520196,"limit":52428800}},"cachereport":{"origin":"mw1432","timestamp":"20231125190914","ttl":1814400,"transientcontent":false}}});});</script> 938 <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Quickselect","url":"https:\/\/en.wikipedia.org\/wiki\/Quickselect","sameAs":"http:\/\/www.wikidata.org\/entity\/Q3927837","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q3927837","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2005-10-13T17:54:33Z","dateModified":"2023-04-17T21:14:23Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/0\/04\/Selecting_quickselect_frames.gif","headline":"selection algorithm to find the kth smallest element in an unordered list"}</script> 939 </body> 940 </html>