انتخاب kامین عنصر کوچک در آرایه نامرتب – به زبان ساده

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 4
Output: 10

روشی که در این مطلب مورد بررسی قرار گرفته، افزونه‌ای از روش «انتخاب سریع» (QuickSelect) است. ایده این روش آن است که به طور تصادفی یک عنصر محوری (Pivot) انتخاب شود. برای پیاده‌سازی پارتیشن تصادفی شده، از تابع تصادفی rand()‎ برای تولید اندیس بین i و r، تعویض یک عنصر با اندیس تصادفی تولید شده با آخرین عنصر و در نهایت، فراخوانی فرایند تقسیم استاندارد که از آخرین عنصر به عنوان محور بهره می‌برد، استفاده شده است.

در ادامه، یک پیاده‌سازی از «انتخاب سریع تصادفی» (Randomized QuickSelect) در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در ++C

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در جاوا

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در پایتون ۳

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در #C

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در PHP

خروجی قطعه کد بالا به صورت زیر است.

K'th smallest element is 5

پیچیدگی زمانی روش ارائه شده در بالا همچنان از درجه O(n2)‎ است. در بدترین حالت، تابع تصادفی همواره یک عنصر گوشه‌ای را انتخاب می‌کند. پیچیدگی زمانی مورد انتظار از QuickSelect از درجه (O(n است.

فیلم مجموعه آموزش برنامه نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش ساختمان داده‌ها با C و ++C (همراه با حل نمونه سوالات کنکور ارشد)
• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده
• معرفی تکنیک‌های مرتب‌سازی (Sorting Techniques) — ساختار داده و الگوریتم ها

^^