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

مرتب‌سازی خارجی (به انگلیسی: External Sorting) اصطلاحی است که به دسته ای از الگوریتم‌های مرتب‌سازی که برای مرتب کردن مقادیر بزرگ داده به کار می‌روند گفته می‌شود. مرتب‌سازی خارجی زمانی به کار می‌رود که محدودیت در حافظه اصلی (عموماً RAM) وجود دارد و درعوض داده به جای این که روی RAM قرار بگیرد روی حافظه‌ای خارجی و کندتر قرار داشته باشد (مثلاً روی Hard drive). مرتب‌سازی خارجی معمولاً از استراتژی مرتب‌سازی ادغامی استفاده می‌کند. در فرایند مرتب‌سازی تکه‌های به اندازه کافی کوچک داده که در حافظه اصلی (RAM) جا می‌گیرند، از فایل مورد نظر خوانده شده، مرتب‌سازی شده و در یک فایل کمکی نوشته و ذخیره می‌شوند. در مرحله ادغام، تکه فایل‌های ذخیره شده با هم ترکیب می‌شوند و یک فایل بزرگ و واحد و در عین حال مرتب شده را می‌سازند. در این حالت زمان دست‌رسی به یک بلوک اطلاعات بر روی حافظه جانبی و خواندن آن‌ها در حافظهٔ اصلی، هزاران برابر بیشتر از زمان دسترسی به حافظهٔ اصلی است، بنابراین معیار سنجش کارایی الگوریتم‌های خارجی را تعداد دسترسی‌ها به حافظهٔ خارجی- دیسک- در نظر می‌گیریم، همچنین زمان پردازش مورد نیاز پس از هر خواندن از حافظه جانبی، یک مقدار ثابت در نظر گرفته می‌شود، چون اندازه میان‌گیری که در حافظه اصلی، این داده را در خود ذخیره می‌کند، مستقل از اندازهٔ داده‌است و ثابت فرض می‌شود.

فرضیات الگوریتم مرتب‌سازی خارجی

در الگوریتم مرتب‌سازی خارجی فرض می‌کنیم:

اطلاعات بر روی فایل‌های حافظهٔ خارجی به صورت ترتیبی ذخیره شده‌است: یعنی برای خواندن رکورد mام باید m-1رکورد قبلی آن خوانده شود.
هر فایل شامل n رکورد است و هر رکورد یک کلید یکتا دارد.
هدف ایجاد فایلی است که رکوردهای آن بر اساس کلیدشان مرتب باشند.
با هر دسترسی به دیسک، یک بلوک به اندازهٔ k رکورد خوانده می‌شود.
تعداد فایل‌هایی که در یک زمان می‌توانند باز باشند حداکثر برابر مقدار ثابت r است.
اندازه حافظه اصلی قابل استفاده- یا همان میان‌گیرها- از مرتبه الگو:عبارت چپ‌چین است.
عملیات مقایسه و محاسبات دیگر فقط در حافظهٔ اصلی انجام می‌شود.

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

الگوریتم مرتب‌سازی ادغامی خارجی مثالی از مرتب‌سازی خارجی می‌باشد، که تکه‌های داده را که در RAM قرار می‌گیرند مرتب‌سازی می‌کند، سپس تکه‌هایی که مرتب شده‌اند را با هم ادغام می‌کند. به‌طور مثال برای مرتب کردن یک فایل با حجم 900MB، فقط 100MB حافظه RAM در اختیار داریم، به صورت زیر عمل می‌کنیم:

100MB از داده را خوانده و روی RAM قرار می‌دهیم و توسط یکی از متدهای مرتب‌سازی مثل مرتب‌سازی سریع آنرا مرتب می‌کنیم.
داده مرتب‌شده را روی هارد دیسک ذخیره می‌کنیم.
این دو مرحله را برای تمام تکه‌های ۱۰۰ مگابایتی که در مراحل بعد می‌خوانیم، انجام می‌دهیم، حالا باید تکه‌های مرتب‌شده را ادغام کنیم تا یک فایل خروجی واحد داشته باشیم.
10MB اول هر فایل مرتب‌شده را در بافر ورودی در RAM می‌ریزیم (۹ فایل با حجم 10MB) و 10MB باقی‌مانده را به بافر خروجی اختصاص می‌دهیم_در عمل اگر بافر خروجی را بزرگتر و بافر ورودی را کمی کوچکتر در نظر بگیریم ممکن است عملکرد بهتری داشته باشیم.
نه مرحله ادغام انجام می‌دهیم و نتیجه را در بافر خروجی ذخیره می‌کنیم. اگر بافر خروجی پر شد، آنرا در فایل نهایی ذخیره می‌کنیم و بافر خروجی را خالی می‌کنیم. اگر هر کدام از ۹ بافر ورودی خالی شدند آنرا با 10MB بعدی از فایل 100MB مربوطه پر می‌کنیم تا زمانی که کل فایل ۱۰۰ مگابایتی تمام شود. این گامی کلیدی است که باعث می‌شود ادغام خارجی به درستی کار کند، چرا که الگوریتم ادغام معمولی، یکباره تکه فایل را می‌خواند در حالیکه هر تکه نباید به‌طور کامل بارگزاری شود، بلکه قسمت‌های پشت سرهم از آن تکه، آن هم در صورت نیاز باید بارگزاری شوند.

الگوریتم کلی مرتب‌سازی ادغامی خارجی

الگوریتم به صورت زیر عمل می‌کند:

فایل ورودی را به دو فایل الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین با حداکثر یک رکورد اختلاف تقسیم می‌کند.
برای الگو:عبارت چپ‌چین مراحل زیر را تکرار می‌کند:

الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین را به عنوان فایل‌های ورودی در نظر می‌گیرد. هر بار، قطعات با شماره‌های یکسان الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین را با یکدیگر ادغام می‌کند. حاصل هر ادغام قطعه‌ای مرتب به طول الگو:عبارت چپ‌چین است_ بجز قطعهٔ آخر که ممکن است طولش کمتر باشد_. این قطعات را یکبار در میان در الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین می‌نویسد.
الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین را به عنوان فایل‌های ورودی و الگو:عبارت چپ‌چین و الگو:عبارت چپ‌چین را به عنوان فایل‌های خروجی در نظر می‌گیرد و مراحل بالا را تکرار می‌کند.

الگو:عبارت چپ‌چین به وسیله استقرا می‌توان نشان داد که در انتهای مرحلهٔ iام هر فایل خروجی دارای قطعات مرتب و به طول الگو:عبارت چپ‌چین است_ بجز حداکثر یک قطعه که طولش از این مقدار کمتر است_. همچنین، تعداد قطعه‌های دو فایل خروجی حداکثر یک واحد اختلاف دارند، بنابراین در انتهای مرحلهٔ الگو:عبارت چپ‌چین یکی از فایل‌های خروجی حاوی تنها یک قطعهٔ مرتب از تمام n زکورد فایل ورودی و دیگری خالی است. با توجه به این که در هر تکرار همهٔ n رکورد موجود یکبار خوانده و یکبار نوشته می‌شود، تعداد دست‌رسی‌ها به دیسک در مجموع برابر الگو:عبارت چپ‌چین است.