الگوریتم تصادفی شناسایی عنصر kام

این الگوریتم از رویکرد یکسانی با مرتب‌سازی سریع بهره می‌برد، عضوی را به عنوان عنصر محوری انتخاب کرده و داده‌ها را بر پایه‌ی آن به دو قسمت تقسیم می‌کند (دو قسمت کمتر و بیشتر از عنصر محوری). اگرچه به جای اینکه همانند مرتب‌سازی سریع بازگشت روی هر دو قسمت داده‌ها انجام شود، در این الگوریتم بازگشت تنها روی یکی از این قسمت‌ها (قسمتی که دارای عضو kام است) انجام می‌شود. به همین دلیل پیچیدگی این الگوریتم از $O (n\log n) $ به $O (n) $ کاهش می‌یابد.

همانند مرتب‌سازی سریع، انتخاب سریع نیز دارای عملکرد حالت متوسط خوبی است، اما به شدت وابسته به عنصرهای محوری انتخاب شده می‌باشد. اگر عنصرهای محوری انتخاب شده مناسب باشند، به این معنا که تعداد داده‌ها را در هر مرحله با نسبت معینی کاهش دهند، تعداد داده‌ها به صورت نمایی کاهش می‌یابد و در نتیجه کارکرد الگوریتم به صورت خطی می‌شود. اگر عنصرهای محوری نامناسب به صورت پیاپی انتخاب شوند، مانند حالتی که در هر مرحله تنها یک عضو از داده‌ها کاسته شود، به بدترین عملکرد الگوریتم با $$O(n^2)$$ منجر خواهد شد. برای مثال این اتفاق در حالتی رخ می‌دهد که برای پیدا کردن بزرگترین عضو در یک سری دادهٔ مرتب شده، عنصر محوری در هر مرحله اولین عضو از داده‌ها باشد. بدین ترتیب به سادگی می‌توان درستی رابطه‌ی زیر را برای بدترین زمان اجرا بررسی کرد: $$ T(n) = \Theta(n) + T(n-1) = \Theta(n^2) $$

برای محاسبه‌ی زمان میانگین، با در نظر گرفتن تصادفی بودن عنصر محوری و فرض (غیر واقعی) اینکه بازگشت همواره در لیست بزرگتر اتفاق می‌افتد می‌توان نوشت: $$ T(n) \leq \Theta(n) + \frac{1}{n} \sum_{i=1}^n T(\max(i,n-i-1)) $$

با در نظر گرفتن $$T(n) \leq cn$$ به عنوان فرض استقرا می‌توان نوشت: $$ T(n) \leq a \cdot n + \frac{1}{n} \sum_{i=1}^n T(\max(i,n-i-1)) $$

$$ \Rightarrow T(n) \leq a \cdot n + \frac{1}{n} \sum_{i=1}^\left \lfloor \frac{n}{2} \right \rfloor T(n-i) + \frac{1}{n} \sum_{\left \lfloor \frac{n}{2} \right \rfloor +1}^n T(i) $$

$$ \Rightarrow T(n) \leq a \cdot n + 2 \times \frac{1}{n} \sum_{\left \lfloor \frac{n}{2} \right \rfloor}^n T(i) $$

$$ \Rightarrow T(n) \leq a \cdot n + 2 \times \frac{1}{n} \sum_{\left \lfloor \frac{n}{2} \right \rfloor}^n c \cdot i $$ و حد بالای جمع سمت راست را به سادگی می‌توان بدست آورد: $$ \sum_{\left \lfloor \frac{n}{2} \right \rfloor}^n i = \sum_{1}^n i- \sum_{1}^\left \lfloor \frac{n}{2} \right \rfloor i = \frac{n \cdot (n+1)}{2} - \frac{\left \lfloor \frac{n}{2} \right \rfloor \cdot ( \left \lfloor \frac{n}{2} \right \rfloor + 1 )}{2}\leq \frac{n^2}{2} - \frac{ \frac{n^2}{4}}{2} = \frac{15}{32} \cdot n^2 $$ چرا که $$\left \lfloor \frac{n}{2} \right \rfloor$$ همواره کوچکتر یا مساوی $$\frac{n}{2}$$ است. بنابراین: $$ \Rightarrow T(n) \leq a \cdot n + \frac{2 \cdot c}{n} \cdot \frac{15}{32} \cdot n^2 = (a + \frac{15}{16} \cdot c) \cdot n $$ در نتیجه به ازای $$c > 16a$$: $$ T(n) = O(n) $$ از طرفی مشخص است که $T(n)$ از $\Omega (n)$ نیز هست. بنابراین: $$ T(n) = \Theta(n) $$

در این الگوریتم تابعی به نام «تقسیم کننده» وجود دارد که می‌تواند یک لیست را به دو بخش (اعضای کوچکتر از یک عنصر خاص و اعضای بزرگتر از آن) تقسیم کند. کد ++C یک تقسیم‌کننده که یک تقسیم بر پایهٔ مقدار موجود در list[pivotIndex] انجام می‌دهد را در زیر می‌توانید مشاهده کنید:

partition.cpp

void partition(int[] list, int left, int right, int pivotIndex)
{
  int pivotValue = list[pivotIndex];
  swap(list[pivotIndex], list[right]);
  int storeIndex = left;
  for(int i = left; i < right; i++)
  {
    if(list[i] < pivotValue)
    {
      swap(list[storeIndex], list[i]);
      storeIndex++;
    }
  }
  swap(list[right], list[storeIndex]);
  return storeIndex;
}

در مرتب‌سازی سریع با مرتب‌سازی هر قسمت به صورت بازگشتی به عملکردی در بهترین حالت با $O(n\log n)$ دست می‌یافتیم. در این الگوریتم از قبل می‌دانیم که عضو مورد نظر ما در کدام یک از قسمت‌ها است و به همین دلیل تنها با یک بازگشت در هر مرحله می‌توانیم به عضو مورد نظر خود برسیم:

selection.cpp

int select(int[] list, int left, int right, int n)
{
   if(left == right)        // آرایه تنها یک عنصر دارد
       return list[left];
   pivotIndex = 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);
}

• انتخاب سریع - ویکی‌پدیا