مرتب‌سازی خارجی

تصویر = این الگوریتم مانند الگوریتم مربت‌سازی ادغامی است با این تفاوت که حافظه کافی در اختیار نیست
مرتب‌سازی خارجی (به انگلیسی: External Sorting) اصطلاحی است که به دسته‌ای از الگوریتم‌های مرتب سازی که برای مرتب کردن مقادیر بزرگ داده به کار می‌روند، اطلاق میشود. مرتب سازی خارجی زمانی به کار میرود که محدودیت در حافظه اصلی (عموما RAM) وجود دارد و درعوض داده به جای این که روی RAM قرار بگیرد روی حافظه‌ای خارجی و کندتر قرار داشته باشد (مثلا روی Hard drive).
مرتب‌سازی خارجی معمولا از استراتژی مرتب‌سازی ادغامی استفاده میکند. در فرایند مرتب سازی تکه‌های به اندازه کافی کوچک داده که در حافظه اصلی (RAM) جا میگیرند، از فایل مورد نظر خوانده شده، مرتب سازی شده و در یک فایل کمکی نوشته و ذخیره میشوند. در مرحله ادغام ، تکه فایل‌های ذخیره شده با هم ترکیب میشوند و یک فایل بزرگ و واحد و در عین حال مرتب شده را میسازند.
در این حالت زمان دست‌رسی به یک بلوک اطلاعات بر روی حافظه جانبی و خواندن آن‌ها در حافظه‌ی اصلی، هزاران برابر بیشتر از زمان دسترسی به حافظه‌ی اصلی است، بنابراین معیار سنجش کارایی الگوریتم‌های خارجی را تعداد دسترسی‌ها به حافظه‌ی خارجی- دیسک- در نظر می‌گیریم، همچنین زمان پردازش مورد نیاز پس از هر خواندن از حافظه جانبی، یک مقدار ثابت در نظر گرفته می‌شود، چون اندازه میان‌گیری که در حافظه اصلی، این داده را در خود ذخیره می‌کند، مستقل از اندازه‌ی داده است و ثابت فرض می‌شود.
فرضیات الگوریتم مرتب‌سازی خارجی
در الگوریتم مرتب‌سازی خارجی فرض می‌کنیم:
اطلاعات بر روی فایل‌های حافظه‌ی خارجی به صورت ترتیبی ذخیره شده است: یعنی برای خواندن رکورد mام باید m-1رکورد قبلی آن خوانده شود.
هر فایل شامل n رکورد است و هر رکورد یک کلید یکتا دارد.
هدف ایجاد فایلی است که رکوردهای آن بر اساس کلیدشان مرتب باشند.
با هر دسترسی به دیسک، یک بلوک به اندازه‌ی k رکورد خوانده می‌شود.
تعداد فایل‌هایی که در یک زمان می‌توانند باز باشند حداکثر برابر مقدار ثابت r است.
اندازه حافظه اصلی قابل استفاده- یا همان میان‌گیرها- از مرتبه است.
عملیات مقایسه و محاسبات دیگر فقط در حافظه‌ی اصلی انجام می‌شود.
مرتب سازی ادغامی خارجی
الگوریتم مرتب‌سازی ادغامی خارجی مثالی از مرتب‌ازی خارجی میباشد ، که تکه‌های داده را که در RAM قرار میگیرند مرتب‌سازی می‌کند، سپس تکه‌هایی که مرتب شده‌اند را با هم ادغام می‌کند. به طور مثال برای مرتب کردن یک فایل با حجم 900MB ، فقط 100 MB حافظه RAM در اختیار داریم ، به صورت زیر عمل میکنیم :
100MB از داده را خوانده و روی RAM قرار می‌دهیم و توسط یکی از متدهای مرتب‌سازی مثل مرتب‌سازی سریع آنرا مرتب میکنیم .
داده مرتب‌شده را روی هارد دیسک ذخیره میکنیم.
این دو مرحله را برای تمام تکه‌های 100 مگابایتی که در مراحل بعد می‌خوانیم، انجام می‌دهیم، حالا باید تکه‌های مرتب‌شده را ادغام کنیم تا یک فایل خروجی واحد داشته باشیم.
10MB اول هر فایل مرتب‌شده را در بافر ورودی در RAM میریزیم (9 فایل با حجم 10MB) و 10MB باقی‌مانده را به بافر خروجی اختصاص میدهیم_در عمل اگر بافر خروجی را بزرگتر و بافر ورودی را کمی کوچکتر در نظر بگیریم ممکن است عملکرد بهتری داشته باشیم.
نه مرحله ادغام انجام می‌دهیم و نتیجه را در بافر خروجی ذخیره می‌کنیم. اگر بافر خروجی پر شد ، آنرا در فایل نهایی ذخیره می‌کنیم و بافر خروجی را خالی می‌کنیم. اگر هر کدام از 9 بافر ورودی خالی شدند آنرا با 10MB بعدی از فایل 100MB مربوطه پر میکنیم تا زمانی که کل فایل 100 مگابایتی تمام شود. این گامی کلیدی است که باعث می‌شود ادغام خارجی به درستی کار کند ، چرا که الگوریتم ادغام معمولی ، یکباره تکه فایل را میخواند در حالیکه هر تکه نباید به طور کامل لود شود ، بلکه قسمت‌های پشت سرهم از آن تکه ، آن هم در صورت نیاز باید لود شوند.
الگوریتم کلی مرتب‌سازی ادغامی خارجی
الگوریتم به صورت زیر عمل می‌کند:
فایل ورودی را به دو فایل و با حداکثر یک رکورد اختلاف تقسیم می‌کند.
برای مراحل زیر را تکرار می‌کند:
و را به عنوان فایل‌های ورودی در نظر می‌گیرد. هر بار، قطعات با شماره‌های یکسان و را با یکدیگر ادغام می‌کند. حاصل هر ادغام قطعه‌ای مرتب به طول است_ بجز قطعه‌ی آخر که ممکن است طولش کمتر باشد_ . این قطعات را یکبار در میان در و می‌نویسد.
و را به عنوان فایل‌های ورودی و و را به عنوان فایل‌های خروجی در نظر می‌گیرد و مراحل بالا را تکرار می‌کند.
به وسیله استقرا می‌توان نشان داد که در انتهای مرحله‌ی iام هر فایل خروجی دارای قطعات مرتب و به طول است_ بجز حداکثر یک قطعه که طولش از این مقدار کمتر است_ . همچنین، تعداد قطعه‌های دو فایل خروجی حداکثر یک واحد اختلاف دارند، بنابراین در انتهای مرحله‌ی یکی از فایل‌های خروجی حاوی تنها یک قطعه‌ی مرتب از تمام n زکورد فایل ورودی و دیگری خالی است. با توجه به این که در هر تکرار همه‌ی n رکورد موجود یکبار خوانده و یکبار نوشته می‌شود، تعداد دست‌رسی‌ها به دیسک در مجموع برابر است.
مرتب‌سازی خارجی چندفازه
مرتب‌سازی چندفازه همان مرتب‌سازی ادغامی است که به جای استفاده از چهار فایل کمکی، از سه فایل کمکی استفاده می‌کند که مراحل آن به شرح ذیل است:
به فایل ورودی کم‌ترین تعداد رکورد را با کلید اضافه می‌کند تا طول آن n برابر iامین عدد فیبوناچی_ _ شود.
فایل ورودی را به دو فایل با اندازه‌های و تقسیم می‌کند_ _.
قدم‌ای زیر را به تعداد M بار تکرار می‌کند:
فرض می‌کند دارای قطعه‌ی مرتب‌شده است_ در ابتدای کار _ که اندازه‌ی هر قطعه‌ی آن است_ در ابتدای کار _ . همچنین دارای قطعه‌ی مرتب‌شده است که اندازه‌ی هر قطعه‌ی آن است و خالی است.
قطعه‌ی مرتب از فایل را با همین تعداد قطعه‌ی مرتب از فایل در هم ادغام کرده و حاصل را در می‌نویسد.
حال خالی، دارای قطعه مرتب به اندازه‌ی است.
نام‌گذاری فایل‌ها را به تناسب تغییر می‌دهد.
جدول زیر نشان‌دهنده چند مرحله از الگوریتم بالا است:
پس از گام
ابتدا
1
2
3