مرتب‌سازی مهره‌ای

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

گام اول

مروری بر الگوریتم

عملیات مرتب سازی مهره‌ای را می‌توان به مهره‌هایی که در یک راستا به موازات یکدیگر (در یک قطب) قرار گرفته‌اند تشبیه کرد. دقیقاً همانند چرتکه. با این حال تعداد مشخصی از مهره‌ها در هر یک ار این قطب‌ها قرار می‌گیرند. در ابتدا معلق بودن مهره‌ها در قطب عمودی ممکن است مفید باشد. در اولین مرحله ترتیب نمایش بدین صورت است که مهره‌ها در n=5 سطر و m=4 قطب عمودی قرار می‌گیرند. اعداد سمت راست هر سطر تعداد مهره‌های موجود در آن سطر را نشان می‌دهد. شماره سطر اول و دوم به دلیل وحود ۳ مهره عدد صحیح و مثبت ۳، و شماره سطر بالا به دلیل. جود ۲ مهره عدد صحیح و مثبت ۲ را نشان می‌دهد. اگر ما بخواهیم که مهره‌ها سقوط کنند، سطرها اعداد صحیح (تعداد مهره‌های سطر جدید) را در مرتب سازی شرکت می‌دهد. سطر اول حاوی بیشترین تعداد مهره در این مجموعه و سطرn ام حاوی کمترین تعداد مهره خواهد بود. اگر در سطرهای ذکر شده یک سری از مهره‌ها در ستون ۱ تا k باشند، ستون‌های k+1 تا m پشت سر هم خالی خواهند شد و این امر برای سطرها بعدی نیز ادامه پیدا خواهد کرد. در عملیات سقوط مهره‌ها، در مثال فیزیکی، در واقع ما به مقادیر بزرگتر در ردیف‌های بالا اجازه داده‌ایم تا به ردیف‌های پایین تر انتشار یابند. اگر مقدار نشان داده شده در سطر a کوچکتر از مقدار مندرج در سطر a+1 باشد نشان گر این است که برخی از مهره‌های سطر a+1 در سطر a سقوط کرده‌اند. این مسلم است که سطر a در آن موقعیت شامل مهره‌ای برای جلوگیری از سقوط مهره‌ها از سطر a+1 نمی‌شود. اساس مکانیزم مرتب سازی مهره‌ای با اساس مرتب سازی شمارشی مشابه‌است. تعداد مهره‌ها در هر ستون مربوط به تعدادی از عناصر با ارزش برابر یا کمتر از شاخص یک ستون است.

گام دوم

پیچیدگی زمانی

مرتب شازی مهره‌ای با سه سطح از پیچیدگی زمانی می‌تواند اجرا شود که عبارت اند از:

(O(1: مهره‌ها به‌طور همرمان در در همان واحد زمان نقل مکان کنند. این یک پیچیدگی انتزاعی است و در عمل قابل اجرا نیست.

(${\sqrt {n}}$)O: در یک مدل واقعی و فیزیکی که با استفاده از گرانش است، مدت زمانی که طول می‌کشد تا مهره‌ها سقوط کنند با جذر حداکثر ارتفاع متناسب است که در انجا n می‌باشد.

(O(n: مهره‌های یک سطر در یک زمان منتقل شده‌اند. این مورد در راه حل‌های سخت افزاری آنالوگ و دیجیتال استفاده می‌شود.

(O(S: جایی که در آن S مجموعه‌ای از اعداد صحیح در مجموعه ورودی است: هر مهره به صورت جداگانه منتقل شده‌است. این مورد زمانی است که مرتب سازی مهره‌ای بدون وجود یک مکانیزم اجرایی برای پیدا کردن فضاهای خالی در زیر مهره‌ها، همانند پیاده‌سازی در نرم‌افزار عمل می‌کند.

در مرتب سازی مهره‌ای نیز همانند مرتب سازی طبقه‌بندی شده، زمان اجرا بهتر از حالت (θ(n log⁡n نخواهد بود. سریع‌ترین عملکرد برای مرتب سازی مقایسه‌ای ممکن است. به دلیل آنکه در مرتب سازی مهره‌ای یک مهره همیشه یک عدد صحیح مثبت است با استفاده از ساختار آن این امر ممکن است.

یادداشت‌ها

طبق قرار داد اگر شماره یک سطر k باشد بدین معناست که ستون‌های ۱ تا k دارای مهره وستون‌های k+1 تا m نیز خالی از مهره می‌باشند.

منابع

• https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/%7Ejaru003/research/publications/journals/beadsort.pdf
• http://en.wikipedia.org/wiki/Bead_sort