نمایش مبدأ برای الگوریتم انتخاب

در [[علوم کامپیوتر]]، یک الگوریتم انتخاب، یک [[الگوریتم]] برای پیدا کردن ''k''امین کوچک‌ترین عدد در یک لیست است (به چنین عددی ''k''امین ''[[مرتبه آماری]]'' گفته می‌شود). این [[الگوریتم|الگوریتم‌ها]] شامل پیدا کردن [[کمینه]]، [[بیشینه]] و [[میانه (آمار)|میانه‌ی]] عناصر است. الگوریتم‌های انتخاب از <math>O(n)</math>، که در بدترین حالت خطی اند، وجود دارند. انتخاب یکی از زیرمسئله‌های مسائل پیچیده‌تر مانند [[مسئله نزدیک‌ترین همسایه]] و [[مسئله یافتن کوتاهترین مسیر]] است.

== انتخاب با مرتب‌سازی ==
انتخاب ممکن است با مرتب کردن لیست و سپس استخراج عنصر دلخواه، به [[الگوریتم مرتب‌سازی|مرتب‌سازی]] تبدیل شود. این روش زمانی کارآمد است که به تعداد زیادی انتخاب از یک لیست نیاز باشد، در موردی که تنها یک بار مقداردهی می‌شود، یک [[مرتب‌سازی]] پرهزینه، همراه با چندین عمل استخراج کم‌هزینه انجام می‌شود. در حالت کلی، این روش نیازمند زمان <math>O(n log n)</math> است، که در آن ''n'' طول لیست است.

== الگوریتم‌های کمینه/بیشینه خطی ==
الگوریتم‌های خطی، از لحاظ زمانی، برای پیدا کردن کمینه‌ها یا بیشینه‌ها این گونه کار می‌کنند که روی لیست تکرار می‌کنند و رد کمینه یا بیشینه تا هر بار نگه می‌دارند.

== الگوریتم کلی انتخاب غیر خطی ==
با کمک ایده‌های مورد استفاده در الگوریتم‌های کمینه/بیشینه، ما می‌توانیم یک الگوریتم کلی ساده، ولی ناکارامد برای پیدا کردن کوچک‌ترین ''k''امین یا بزرگ‌ترین ''k'' عنصر در یک لیست بدهیم، که نیاز به زمان <math>O(kn)</math> دارد، که وقتی ''k'' کوچک باشد مؤثر است. برای انجام دادن آن، ما به سادگی کوچک‌ترین/بزرگ‌ترین مقدار را می‌یابیم و آن را به ابتدای بازه حرکت می‌دهیم تا به اندیس دلخواه برسیم. این کار را می‌توانیم به عنوان یک [[مرتب‌سازی انتخابی]] ناتمام ببینیم. در اینجا الگوریتم بر اساس کمینه را می‌بینیم:

{{چپ‌چین}}
  '''function''' select(list[1..n], k)
  '''for''' i '''from''' 1 '''to''' k
  minIndex = i
  minValue = list[i]
  '''for''' j '''from''' i+1 '''to''' n
  '''if''' list[j] <minValue
  minIndex = j
  minValue = list[j]
  swap list[i] and list[minIndex]
  '''return''' list[k]
{{پایان چپ‌چین}}

دیگر مزیت‌های این روش عبارتند از:
* بعد از پیدا کردن کوچک‌ترین ''j''امین عنصر، برای پیدا کردن کوچک‌ترین ''k''امین عنصر، تنها زمان (O(''j'' + (''k''-''j'')<sup>2</sup> یا برای ''k'' ≤ ''j'' تنها زمان <math>O(k)</math> مورد نیاز است.
* در رویه‌ای که بر پایهٔ افراز است و به [[دسترسی تصادفی]] نیاز دارد، می‌توان از داده‌ساختار [[لیست پیوندی]] برای پیاده‌سازی استفاده کرد.

== الگوریتم کلی انتخاب بر پایهٔ افراز ==
یک الگوریتم فراگیر انتخاب که در عمل کارآمد است، اما در بدترین حالت کارایی ضعیفی دارد، توسط ابداع‌کنندهٔ [[مرتب‌سازی سریع]]، ''سی. اِی. آر هوار''، ارائه شده‌است. این الگوریتم به نام '''الگوریتم انتخاب هوار''' یا [[انتخاب سریع]] شناخته می‌شود.

در مرتب‌سازی سریع، یک زیررَویه به نام افراز وجود دارد که می‌تواند در زمان خطی، یک لیست را به دو بخش <code>left</code> و <code>right</code> تقسیم‌بندی می‌کند که یک گروه کوچک‌تر از یک عنصر خاص و گروه دیگر بزرگ‌تر یا مساوی آن عنصر خاص هستند. اینجا سودوکدی را می‌بینیم که یک افراز را برای عنصر <code>list[pivotIndex]</code> اجرا می‌کند:

{{چپ‌چین}}
  '''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
  '''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
{{پایان چپ‌چین}}

در مرتب‌سازی سریع، ما به صورت بازگشتی هر دو شاخه را در بهترین حالت در زمان <math>O(n log n)</math> مرتب می‌کنیم. اما، وقتی که انتخاب انجام می‌دهیم، از می‌دانیم که عنصر مورد نظر ما در کدام افراز قرار دارد، چون محور (انگلیسی: pivot) در محل نهایی مرتب‌شدهٔ خود قرار دارد و از همهٔ عناصر قبل از خود بزرگ‌تر و از همهٔ عناصر بعد از خود کوچک‌تر یا مساوی است. بنابراین یک فراخوانی بازگشتی می‌تواند مکان یک عنصر دلخواه را در افراز درست بیابد:

{{چپ‌چین}}
  '''function''' select(list, left, right, k)
  '''if''' left = right // If the list contains only one element
  '''return''' list[left]  // Return that element
  select pivotIndex between left and right
  pivotNewIndex := partition(list, left, right, pivotIndex)
  pivotDist := pivotNewIndex - left + 1
      // The pivot is in its final sorted position,
      // so pivotDist reflects its 1-based position if list were sorted
  '''if''' pivotDist = k
  '''return''' list[pivotNewIndex]
  '''else if''' k <pivotDist
  '''return''' select(list, left, pivotNewIndex - 1, k)
  '''else'''
  '''return''' select(list, pivotNewIndex + 1, right, k - pivotDist)
{{پایان چپ‌چین}}

<!--- یک بند رو فعلاً جا انداختم به همراه کد--->

مانند مرتب‌سازی سریع، کارایی الگوریتم به محوری که انتخاب می‌شود بستگی دارد. اگر محورهای نامناسب به‌طور متوالی انتخاب شوند، این رویه به انتخاب بر پایهٔ کمینه، که قبلاً گفته شد، تنزل پیدا می‌کند و در نتیجه به زمان (O(''n''<sup>2</sup> نیاز پیدا خواهد کرد.

== الگوریتم کلی انتخاب به صورت خطی - الگوریتم میانهٔ میانه‌ها ==
<!---باید جدول را درست کنم--->
یک الگوریتم با بدترین [[زمان اجرای خطی]] برای حالت کلی انتخاب ''k''امین بزرگ‌ترین عنصر توسط ''بلوم''، ''فلوید''، ''پرت''، ''ریوست'' و ''ترجان'' در مقاله سال ۱۹۳۷ با نام «حدود زمانی برای انتخاب» منتشر شد. گاهی از این الگوریتم با نام '''BFPRT'''، که حروف اول [[نام خانوادگی]] نویسندگان آن است، یاد می‌شود. این الگوریتم بر اساس الگوریتم انتخاب سریع کار می‌کند و هم‌چنین به نام الگوریتم [[میانه میانه‌ها]] شناخته می‌شود.

هرچند انتخاب سریع به‌طور میانگین دارای زمان خطی است، زمانی که محورهای ضعیفی استفاده شوند می‌تواند به زمان از درجه دوم نیاز پیدا کند (حالتی را در نظر بگیرید که در هر گام، محور در نزدیکی کوچک‌ترین عنصر انتخاب شود). راه چاره برای اینکه آن را به <math>O(n)</math> در ''بدترین'' حالت تبدیل کنیم این است که به‌طور پیوسته در هر گام محور ''مناسب'' را بیابیم. یک محور خوب باید به گونه‌باشد که بتوانیم اطمینان داشته باشیم نسبت ثابتی از عناصر قبل از آن و بعد از آن قرار بگیرند.

الگوریتم ''انتخاب'' لیست را به گروه‌هایی شامل پنج عنصر تقسیم می‌کند. (فعلاً با عناصر باقی‌مانده کاری نداریم). سپس، برای هر گروه پنج‌تایی، میانه محاسبه می‌شود (اگر آن پنج مقدار داخل ثبّات‌ها بارگذاری شوند و مقایسه شوند، عملیات به‌طور بالقوه بسیار سریع انجام می‌شود). (اگر مرتب‌سازی به صورت درجا صورت گیرد، این میانه‌ها به یک بلوک پیوسته در لیست منتقل می‌شوند) ''انتخاب'' به صورت بازگشتی در این زیرلیست‌های ''n''/5 عنصری فراخوانده می‌شود تا مقدار واقعی میانه یافت شود. سرانجام، ''میانهٔ میانه‌ها'' به عنوان محور انتخاب می‌شود.

== ویژگی‌های محور ==
محور انتخاب شده، از نیمی از عناصر لیست میانه‌ها بزرگ‌تر و از نیمهٔ دیگر کوچک‌تر است، به‌طوری‌که در هر نیمه <math>n/10</math> عنصر <math>(1/2 * (n/5))</math> قرار دارند. هر کدام از این عناصر، میانهٔ ۵ عنصر است و از ۲ عنصر کوچک‌تر و از ۲ عنصر در خارج از بلوک بزرگ‌تر است. پس، محور کوچک‌تر از <math>3(n/10)</math> عناصر خارج از بلوک است، و از <math>3(n/10)</math> عنصر دیگر خارج از بلوک بزرگ‌تر است. بنا بر این، میانهٔ انتخاب شده، عناصر را به مکانی بین ۳۰٪/۷۰٪ و ۷۰٪/۳۰٪ تقسیم می‌کند. این کار به ما اطمینان می‌دهد که رفتار الگوریتم در بدترین حالت خطی است. برای به دست آوردن شهود کافی به جدول زیر دقت کنید:

{|class="wikitable" border=1
|+ یک تکرار روی لیست {۹۹... ,۰٬۱,۲٬۳}
!
| bgcolor=gray|12||||bgcolor=gray|15||||bgcolor=gray|11||||bgcolor=gray|2||||bgcolor=gray|9||||bgcolor=gray|5||||bgcolor=gray|0||||bgcolor=gray|7||||bgcolor=gray|3||||bgcolor=gray|21||||bgcolor=gray|44||||bgcolor=gray|40||||bgcolor=gray|1||||bgcolor=gray|18||||bgcolor=gray|20||||bgcolor=gray|32||||bgcolor=gray|19||||bgcolor=gray|35||||bgcolor=gray|37||||bgcolor=gray|۳۹
|-
!
| bgcolor=gray|13||||bgcolor=gray|16||||bgcolor=gray|14||||bgcolor=gray|8||||bgcolor=gray|10||||bgcolor=gray|26||||bgcolor=gray|6||||bgcolor=gray|33||||bgcolor=gray|4||||bgcolor=gray|27||||bgcolor=white|49||||bgcolor=gray|46||||bgcolor=white|52||||bgcolor=gray|25||||bgcolor=white|51||||bgcolor=gray|34||||bgcolor=gray|43||||bgcolor=white|56||||bgcolor=white|72||||bgcolor=white|۷۹
|-
! میانه‌ها
| bgcolor=gray|17||||bgcolor=gray|23||||bgcolor=gray|24||||bgcolor=gray|28||||bgcolor=gray|29||||bgcolor=gray|30||||bgcolor=gray|31||||bgcolor=gray|36||||bgcolor=gray|42||||bgcolor=red|47||||bgcolor=white|50||||bgcolor=white|55||||bgcolor=white|58||||bgcolor=white|60||||bgcolor=white|63||||bgcolor=white|65||||bgcolor=white|66||||bgcolor=white|67||||bgcolor=white|81||||bgcolor=white|۸۳
|-
!
| bgcolor=gray|22||||bgcolor=gray|45||||bgcolor=gray|38||||bgcolor=white|53||||bgcolor=white|61||||bgcolor=gray|41||||bgcolor=white|62||||bgcolor=white|82||||bgcolor=white|54||||bgcolor=white|48||||bgcolor=white|59||||bgcolor=white|57||||bgcolor=white|71||||bgcolor=white|78||||bgcolor=white|64||||bgcolor=white|80||||bgcolor=white|70||||bgcolor=white|76||||bgcolor=white|85||||bgcolor=white|۸۷
|-
!
| bgcolor=white|96||||bgcolor=white|95||||bgcolor=white|94||||bgcolor=white|86||||bgcolor=white|89||||bgcolor=white|69||||bgcolor=white|68||||bgcolor=white|97||||bgcolor=white|73||||bgcolor=white|92||||bgcolor=white|74||||bgcolor=white|88||||bgcolor=white|99||||bgcolor=white|84||||bgcolor=white|75||||bgcolor=white|90||||bgcolor=white|77||||bgcolor=white|93||||bgcolor=white|98||||bgcolor=white|۹۱
|-
|}
(راهنمای رنگ‌های جدول: قرمز = «(یکی از دو حالت ممکن) میانهٔ میانه‌ها»، خاکستری = «شماره <قرمز»، سفید = «شماره> قرمز»)

در جدول بالا، برای وضوح بیشتر ۵-تایی‌ها بر اساس میانه مرتب شده‌اند. مرتبسازی چندتایی‌ها لزومی ندارد، زیرا ما تنها به میانه برای استفاده به عنوان عنصر محور نیاز داریم.

توجه داشته باشید که تمام عناصر بالا/چپ خانهٔ قرمز (۳۰٪ از ۱۰۰ عنصر) کوچک‌تر از قرمز، و تمام عناصر پایین/راست خانهٔ قرمز (۳۰٪ دیگر از ۱۰۰ عنصر) بزرگتر از قرمز هستند.

=== اثبات زمان اجرای (O(n ===
<!--- بعداً تکمیل شود--->
محاسبهٔ میانه به‌طور بازگشتی، در بدترین حالت از درجه خطی بیشتر نخواهد شد، زیرا لیست میانه‌ها ۲۰٪ از اندازهٔ لیست است، در حالی که فراخوانی بازگشتی دیگر حداکثر روی ۷۰٪ لیست لیست اجرا می‌شود. بنا بر این زمان اجرا به صورت زیر می‌شود:

{{چپ‌چین}}
  T(''n'') ≤ T(''n''/5) + T(7''n''/10) + O(''n'')
{{پایان چپ‌چین}}

زمان (O(''n'' ناشی از عمل افراز کردن است (ما هر عنصر را به تعداد دفعات ثابتی ملاقات می‌کنیم، تا آن‌ها را به گروه‌های (O(n دسته‌بندی کنیم و هر میانه را در زمان (O(n به دست آوریم. به این ترتیب می‌توان نشان داد که
{{چپ‌چین}} T(''n'')&nbsp;≤&nbsp;c*n*(1&nbsp;+&nbsp;(9/10)&nbsp;+&nbsp;(9/10)<sup>2</sup>&nbsp;+&nbsp;...)&nbsp;=&nbsp;O(''n'').{{پایان چپ‌چین}}

== منابع ==
<!--- [[ویکی‌پدیا:پانویس‌ها]] را بخوانید. در وسط مقاله از<ref>منبع</ref> به عنوان منبع استفاده کنید -->{{پانویس}}
* [[مانوئل بلوم|M. Blum]], [[رابرت فلوید|R.W. Floyd]], [[Vaughan Ronald Pratt|V. Pratt]], [[رونالد ریوست|R. Rivest]] and [[رابرت تارجان|R. Tarjan]], "Time bounds for selection," ''J. Comput. System Sci''. 7 (1973) 448-461.
* K. C. Kiwiel. On Floyd and Rivest’s SELECT Algorithm, ''Theoretical Computer Sci.'' 347 (2005) 214-238.
* [[دانلد کنوت]]. ''[[هنر برنامه‌نویسی رایانه]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0|en}}. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
* [[توماس اچ کورمن]]،  [[Charles E. Leiserson]], [[رونالد ریوست]]،  and [[کلیفورد استین]]. ''[[مقدمه‌ای بر الگوریتم‌ها]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7|en}}. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.
* {{یادکرد-ویکی
|پیوند=http://en.wikipedia.org/w/index.php?title=Selection_algorithm&oldid=461888724
|عنوان=Selection Algorithm
|زبان=انگلیسی
|بازیابی= ۲۵ نوامبر ۲۰۱۱
}}

== پیوند به بیرون ==
<!-- این مقاله فعلاً ناقص است و به عنوان تمرین دانشجویی تکمیل می‌گردد. لطفاً تا تاریخ ۱۵ آذر ۱۳۹۰ از ویرایش این صفحه خودداری نمایید -->
<!--- رده‌بندی --->

<!--- میان ویکی--->

[[رده:الگوریتم انتخاب]]
[[رده:الگوریتم‌ها]]
[[رده:نظریه گراف]]