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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مرتب سازی مهره ای یک الگوریتم مرتب سازی طبیعی است که در سال ۲۰۰۲ توسط جاشوا جی. آرولاناندهام، کریستیان سورین کالود و مایکل جان دینین توسعه یافته‌است و در بولتن انجمن اروپایی برای علم کامپیوتر نظری منتشر شده‌است. هر دو پیاده سازی سخت افزارهای دیجیتال و آنالوگ مرتب سازی مهره‌ای دارای پیچیدگی زمانی (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 نیز خالی از مهره می‌باشند.

منابع[ویرایش]