انتخاب درونگرا

انتخاب درونگرا

رده	الگوریتم انتخاب
ساختمان داده	آرایه
کارایی بدترین حالت	$O(n)$
کارایی بهترین حالت	$O(n)$

در علوم رایانه، انتخاب درونگرا(به انگلیسی: Introselect، کوتاه‌شده‌ی introspective selection) یک الگوریتم انتخاب با ترکیب انتخاب سریع و میانه میانه‌ها است که عملکردی سریع در حالت متوسط و عملکردی بهینه در بدترین حالت ممکن را دارد. انتخاب درونگرا بسیار شبیه به مرتب‌سازی درونگرا می‌باشد و هر دو از روش مشابهی با الگوریتم‌های مرتب‌سازی سریع و انتخاب سریع بهره می‌گیرند. هر‌دوی این الگوریتم‌ها با الگوریتم سریع (مرتب‌سازی سریع یا انتخاب سریع) شروع می‌شوند که کارکرد حالت متوسط خوب و سربار محاسبات کمی دارند، اما در صورتی که روند پیش‌روی این الگوریتم ها کند باشد، از الگوریتم دیگری که بهینه ولی دارای سربار محاسباتی بیشتری است استفاده می‌کنند. هر دوی این الگوریتم‌ها توسط دیوید ماسر (David Musser) در (chelsea marrs 1997) با هدف ارائه الگوریتم‌های جنریک برای کتابخانه استاندارد سی++ معرفی شدند. هر دوی این الگوریتم ها در حالت میانگین سریع و در بدترین حالت ممکن بهینه هستند.

الگوریتم

مرتب‌سازی درونگرا کارکردی قابل مقایسه با مرتب‌سازی سریع دارد و در عین حال در بدترین حالت ممکن، با ترکیب مرتب‌سازی سریع و مرتب‌سازی هرمی رفتاری از O(n log n) را از خود نشان می‌دهد. مرتب‌سازی درونگرا با مرتب‌سازی سریع شروع می‌شود و به کارکردی مشابه مرتب‌سازی سریع می‌رسد، اما در صورتی که روند پیش‌روی این الگوریتم کند باشد، باز گشته و از مرتب‌سازی هرمی(که کارکرد بدترین حالت بهینه شده‌ای دارد) کمک می‌گیرد. به صورت مشابه انتخاب درونگرا نیز از ترکیب انتخاب سریع با میانه میانه‌ها استفاده کرده تا در بدترین حالت ممکن رفتاری خطی را از خود نشان دهد و کارکردی مشابه انتخاب سریع داشته باشد.

انتخاب درونگرا به صورت خوشبینانه با انتخاب سریع شروع به کار میکند و تنها در صورتی که دنباله‌ی بازگشتی پس از بازگشت به تعداد زیاد، پیشرفت قابل قبولی را حاصل نکند به الگوریتم میانه میانه‌ها(Blum-Floyd-Pratt-Rivest-Tarjan) تغییر رَویه می‌دهد. تغییر استراتژی ویژگی اصلی انتخاب درونگرا می‌باشد. تغییر رویه تنها با در نظر گرفتن تعداد ثابتی بازگشت به اندازه کافی خوب نیست، چرا که در این صورت الگوریتم روی تمامی لیست‌هایی که به اندازه‌ی کافی بزرگ باشند تغییر رویه خواهد داد. ماسر تعدادی راه حل ساده را برای حل این مسئله بیان میکند:

• در صورتی که k بازگشت صورت گرفت بدون اینکه طول لیس نصف شود برای یک k کوچک، به الگوریتم خطی تغییر رویه بدهید.
• مجموع اندازه تمام تقسیم‌های انجام شده تا کنون را در نظر بگیرید. اگر این مجموع از طول لیست اصلی ضرب در یک ثابت مثبت و کوچک k بزرگتر شد، به الگوریتم خطی تغییر رویه بدهید.

هر دو روش عمق بازگشت‌ها را محدود به ⌈log n⌉ = k O(log n) کرده و در مجموع زمان اجرا از O(n) خواهد شد.

منابع

• Musser, David (1997). "Introspective Sorting and Selection Algorithms". Software: Practice and Experience. Wiley. ۲۷ (۸): ۹۸۳–۹۹۳. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#. Archived from the original on 16 July 2012. Retrieved 6 April 2016.