موضوع مقاله: مرتب‌سازی گسترش‌یافته | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی گسترش‌یافته | مقدمه: این الگوریتم، مفاهیمی از مرتب‌سازی‌های توزیع شده مانند مرتب‌سازی مبنایی و سطلی را با مفاهیم مرتب‌سازی‌های سریع و ترکیبی تلفیق می‌کند. | ## بخش 1: مرتب‌سازی گسترش‌یافته | در نتایج تجربی، این الگوریتم در اجرا، بسیار کارامد تر از الگوریتم‌های سنتی مانند مرتب‌سازی سریع به ویژه در ارائه ساختارهای توزیع شده نشان داده شده‌است. مرتب‌سازی سریع یک عنصر محوری را درلیست شناسایی می‌کند و لیست را به دو زیر لیست تقسیم می‌کند:عناصر بزرگتر از عنصر محوری وعناصر کوچکتر ازعنصر محوری. مرتب‌سازی گسترش یافته این ایده را به صورت تقسیم بندی لیست به n/cپارتیشن در هر گام تعمیم می‌دهد، که nتعداد عناصر لیست وc ثابت کوچک است (در عمل در مقایسه‌های کند، معمولاً بین ۴ تا ۸ است؛ ولی در مقایسه‌های سریع c مقدار بزرگتری است). ابتدا بزرگترین و کوچکترین مقادیر را وارد لیست می‌کند سپس ناحیه بین این دو را به n/c ظرف بااندازه مساوی تقسیم می‌کند. در مواقعی که ذخیره‌سازی یک مسئله مهم است، این الگوریتم می‌تواند در هر مرحله از تقسیم بازگشتی به داشتن بزرگترین ظرف کمک کند و باعث می‌شود این روند تقسیم چندین مرحله داشته باشد، اگرچه این کار باعث تکراربیشتر می‌شود ولی خطاهای ذخیره‌سازی را کاهش می‌دهد و باعث می‌شود که الگوریتم سریع تر اجرا شود. درمواردی که تعداد ظرف‌ها حداقل برابر تعداد عناصر است، مرتب‌سازی گسترش یافته به مرتب‌سازی سطلی تخریب می‌شود و مرتب‌سازی به اتمام می‌رسد. الگوریتم از آزمون‌های اکتشافی برای تعیین اینکه ایا هر ظرف می‌تواند توسط این الگوریتم یا الگوریتم‌های دیگر، به‌طور کارامدتری مرتب شود، استفاده می‌کند. | ## بخش 2: مرتب‌سازی گسترش‌یافته | این الگوریتم نیز مانند الگوریتم‌های توزیع شده دیگر نقطه ضعفی دارد و آن این است که برنامه‌نویس به ابزاری برای تبدیل هرعنصربه یک کلید عددی نیاز دارد و هدف آن شناسایی این است که هرکدام ازعناصر در کدام ظرف می‌افتند. اگرچه برای عناصر با طول متغیر مانند رشته‌ها (با توجه به اینکه هر عدد باتعداد بی‌نهایتی از مقادیر مینیمم دنبال می‌شود و برای هرنوع داده‌ای دارای یک ارایش کلی می‌باشد) این عملیات برای پیاده‌سازی صحیح بسیار سخت تر از یک تابع مقایسه‌ای ساده به ویژه در ساختارهای پیچیده‌است. پیاده‌سازی ضعیف این تابع مقداری می‌تواند منجر به کلاستربندی شود که به کارایی الگوریتم آسیب می‌رساند. کارایی بدترین حالت الگوریتم مرتب‌سازی گسترش یافته بستگی به این دارد که این الگوریتم در نهایت کدام مرتب‌سازی را تبدیل به ظرف‌های کوچک می‌کند. برای الگوریتم‌هایی که بدترین حالت شان O(nlogn) است مانند مرتب‌سازی ادغامی و مرتب‌سازی هرمی و برای الگوریتم‌هایی که بدترین حالت شان O(n^۲)می‌باشد مانند مرتب‌سازی سریع، مقدار O(nlogn) می‌باشد. آزمایش‌هایی که برای مقایسه نسخه بهینه مرتب‌سازی گسترش یافته با مرتب‌سازی بهینه C++انجام شدند، با مرتب‌سازی درونگرا پیاده‌سازی شدند. این الگوریتم در ساده‌ترین شکلش یک الگوریتم درجا نیست که ازفضای اضافی O(n) استفاده کند. | ## بخش 3: مرتب‌سازی گسترش‌یافته | درفرم حافظه دار، از حافظه کمتری استفاده می‌شود و در استفاده از حافظه با حداکثرشمارش ظرف‌ها به تعداد حداکثر بازگشت‌ها یک کران بالا وجود دارد که تا تبدیل اندازه کلیدها از بایت به کیلوبایت تمام می‌شود. اگرچه در این فرم نسبت به مرتب‌سازی سریع و مرتب‌سازی هرمی از فضای بیشتری استفاده می‌شود، ولی نسبت به فرم‌های اولیه مرتب‌سازی ادغامی که از فضای کمکی برابر با فضای اشغال شده توسط لیست‌ها استفاده می‌کند، به‌طور قابل ملاحظه‌ای از حافظه کمتری استفاده می‌نماید. مرتب‌سازی گسترش یافته در مورد مسائل بسیار بزرگ که در حافظه جای نمی‌گیرند ونیازمند دسترسی به دیسک هستند، بسیار کارامد عمل می‌کند. این نتیجه می‌تواند بدین صورت فراهم شود که اگر اندازه ظرف‌ها بعد از اولین تکرار بیشتر از برخی مقادیر ثابت بود، الگوریتم مرتب‌سازی گسترش یافته حداقل ۲ بار تکرارشود. اگر داده‌ها درهمه اوقات بر روی برخی توابع پیوسته انتگرال پذیر شناخته شوند این اصلاح مرتب‌سازی گسترش یافته می‌تواند به برخی بهبودهای کارایی بر روی الگوریتم اصلی نائل شود ومی تواند بدترین حالت بهتری داشته باشد. | ## جمع‌بندی | اگر این محدودیت نتواند وابستگی داشته باشد، این تغییر یک سربار اضافی کوچک را به الگوریتم اضافه می‌کند وکوچک تر می‌شود.