انتخاب سریع
From Wikipedia, the free encyclopedia
در علوم رایانه، انتخاب سریع یک الگوریتم انتخاب برای پیدا کردن k امین عضو کوچک یک لیست است. همانند مرتبسازی سریع، این الگوریتم نیز توسط تونی هور توسعه داده شده و به همین دلیل به اسم الگوریتم انتخاب تونی هور نیز شناخته میشود.[1] همانند مرتبسازی سریع، این الگوریتم نیز بهینه و دارای عملکرد حالت متوسط خوبی میباشد، اما عملکرد بدترین حالت ممکن این الگوریتم ضعیف است. انتخاب سریع و انواع دیگر آن از جمله الگوریتمهای انتخابی هستند که در پیادهسازیهای بهینه شده مورد استفاده قرار میگیرند.
![]() کارکرد انتخاب سریع بر روی یک فهرست تصادفی از اعداد برای انتخاب 22امین کوچکترین عضو. | |
رده | الگوریتم انتخاب |
---|---|
ساختمان داده | آرایه |
کارایی بدترین حالت | |
کارایی بهترین حالت | |
کارایی متوسط |
انتخاب سریع از رویکرد یکسانی با مرتبسازی سریع بهره میبرد، عضوی را به عنوان عنصر محوری انتخاب کرده و دادهها را بر پایهٔ آن به دو قسمت تقسیم میکند (دو قسمت کمتر و بیشتر از عنصر محوری). اگرچه به جای اینکه همانند مرتبسازی سریع بازگشت روی هر دو قسمت دادهها انجام شود، در انتخاب سریع بازگشت تنها روی یکی از این قسمتها (قسمتی که دارای عضو k ام است) انجام میشود. به همین دلیل پیچیدگی این الگوریتم از به
کاهش مییابد.
همانند مرتبسازی سریع، انتخاب سریع نیز معمولاً به صورت الگوریتم درجا پیادهسازی میشود، و علاوه بر پیدا کردن k امین عضو، دادهها را نیز به صورت ناحیهای مرتب میسازد. برای اطلاعات بیشتر دربارهٔ ارتباط انتخاب سریع با مرتبسازی به الگوریتم انتخاب رجوع کنید.