انتخاب سریع
الگوریتم

در انتخاب سریع یک زیر رَویه به نام "تقسیم کننده" وجود دارد که می‌تواند یک لیست را به دو بخش (اعضای کوچکتر از یک عنصر خاص و اعضای بزرگتر از آن) تقسیم کند. شبه کد یک تقسیم‌کننده که یک تقسیم بر پایهٔ [list[pivotIndex انجام می‌دهد را در زیر می‌توانید مشاهده کنید:
function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex
در مرتب‌سازی سریع با مرتب‌سازی هر قسمت به صورت بازگشتی به عملکردی در بهترین حالت با  O(nlogn) دست می‌یافتیم. در انتخاب سریع از قبل می‌دانیم که عضو مورد نظر ما در کدام یک از قسمت‌ها است و به همین دلیل تنها با یک بازگشت در هر مرحله می‌توانیم به عضو مورد نظر خود برسیم:
// Returns the n-th smallest element of list within left..right inclusive
  // (i.e. left <= n <= right).
  // The search space within the array is changing for each round - but the list
  // is still the same size. Thus, n does not need to be updated with each round.
  function select(list, left, right, n)
     if left = right        // If the list contains only one element,
         return list[left]  // return that element
     pivotIndex  := ...     // select a pivotIndex between left and right,
                            // e.g., left + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)
شباهت این الگوریتم به مرتب‌سازی سریع قابل توجه است: این الگوریتم علاوه بر یک انتخاب کننده، یک مرتب کنندهٔ جزئی نیز هست. در واقع این الگوریتم یک مرتب‌سازی سریع را به نحوی انجام می‌دهد که تنها  O(logn) از  O(n) قسمت داده‌ها مرتب می‌شوند. این رویهٔ ساده دارای عملکردی خطی است و همانند مرتب‌سازی سریع، در عمل نیز از عملکرد خوبی برخوردار است. از آنجایی که می‌توان از بازگشت دم بودن این الگوریتم با یک حلقه به صورت زیر صرف نظر کرد این الگوریتم یک الگوریتم درجا با سربار حافظهٔ ثابت است:
function select(list, left, right, n)
     loop
         if left = right
             return list[left]
         pivotIndex := ...     // select pivotIndex between left and right
         pivotIndex := partition(list, left, right, pivotIndex)
         if n = pivotIndex
             return list[n]
         else if n < pivotIndex
             right := pivotIndex - 1
         else
             left := pivotIndex + 1
در صورتی که از پیاده‌سازی الگوریتم به صورت درجا صرف نظر کنیم تمامی توابع بالا را به صورت زیر می‌توان خلاصه کرد:
QuickSelect(A, k)
   let r be chosen uniformly at random in the range 1 to length(A)
   let pivot = A[r]
   let A1, A2 be new arrays
   # split into a pile A1 of small elements and A2 of big elements
   for i = 1 to n
     if A[i] < pivot then
       append A[i] to A1
     else if A[i] > pivot then
       append A[i] to A2
     else
       # do nothing
   end for
   if k <= length(A1):
     # it's in the pile of small elements
     return QuickSelect(A1, k)
   else if k > length(A) - length(A2)
     # it's in the pile of big elements
     return QuickSelect(A2, k - (length(A) - length(A2))
   else
     # it's equal to the pivot
     return pivot
همانطور که در شبه کد مشاهده می‌کنید برای پیدا کردن k امین عضو کوچک، در هر مرحله لیست ما به دو لیست شامل اعضای بزرگتر و کوچکتر از pivot (عنصر محوری) تقسیم می‌شود (عنصر محوری به صورت تصادفی انتخاب می‌شود). در صورتی که طول لیست اول کوچکتر یا مساوی k باشد، یعنی k امین عنصر در لیست داده‌های کوچکتر از عنصر محوری قرار دارد و الگوریتم به صورت بازگشتی روی این ناحیه انجام می‌شود. در صورتی که k از طول لیست اولیه منهای طول لیست دوم بزرگتر باشد، k امین عضو در لیست دوم قرار دارد و در نتیجه بازگشت روی این بخش انجام می‌گیرد. اگر هیچ یک از شروط قبلی برقرار نباشند به این معناست که k امین عضو در واقع همان عنصر محوری انتخاب شده می‌باشد.