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

در این مطلب، روش نوشتن برنامه‌ای که kامین عنصر کوچک در آرایه نامرتب را پیدا کند، مورد بررسی قرار گرفته است. از همین روش می‌توان برای پیدا کردن kامین عنصر بزرگ در آرایه نامرتب نیز استفاده کرد. فرض می‌شود که یک آرایه و یک عدد K داده شده است. k کوچک‌تر از اندازه آرایه است. اکنون نیاز است که kاُمین عنصر کوچک‌تر در آرایه داده شده پیدا شود. همچنین، گفته شده که همه عناصر آرایه محدود هستند. شایان ذکر است، پیاده‌سازی روش آموزش داده شده در این مطلب، در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است. مثال زیر در این راستا قابل توجه است.

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 است.

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

کلیک کنید

فرض بر این است که در تحلیل‌ها، «مولد اعداد تصادفی» (Random Number Generator) دارای احتمال یکسانی برای تولید اعداد در رنج ورودی است.

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

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

^^