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

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

• اطلاعات بر روی فایل‌های حافظهٔ خارجی به صورت ترتیبی ذخیره شده‌است: یعنی برای خواندن رکورد mام باید m-1رکورد قبلی آن خوانده شود.
• هر فایل شامل n رکورد است و هر رکورد یک کلید یکتا دارد.
• هدف ایجاد فایلی است که رکوردهای آن بر اساس کلیدشان مرتب باشند.
• با هر دسترسی به دیسک، یک بلوک به اندازهٔ k رکورد خوانده می‌شود.
• تعداد فایل‌هایی که در یک زمان می‌توانند باز باشند حداکثر برابر مقدار ثابت r است.
• اندازه حافظه اصلی قابل استفاده- یا همان میان‌گیرها- از مرتبه ${\displaystyle O(1)}$
  است.
• عملیات مقایسه و محاسبات دیگر فقط در حافظهٔ اصلی انجام می‌شود.

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

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

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

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

1. فایل ورودی را به دو فایل ${\displaystyle f_1}$
   و ${\displaystyle f_2}$
   با حداکثر یک رکورد اختلاف تقسیم می‌کند.
2. برای ${\displaystyle i=1,2,....,M}$
   مراحل زیر را تکرار می‌کند:

• ${\displaystyle f_1}$
  و ${\displaystyle f_2}$
  را به عنوان فایل‌های ورودی در نظر می‌گیرد. هر بار، قطعات با شماره‌های یکسان ${\displaystyle f_1}$
  و ${\displaystyle f_2}$
  را با یکدیگر ادغام می‌کند. حاصل هر ادغام قطعه‌ای مرتب به طول ${\displaystyle 2^i}$
  است_ بجز قطعهٔ آخر که ممکن است طولش کمتر باشد_. این قطعات را یکبار در میان در ${\displaystyle g_1}$
  و ${\displaystyle g_2}$
  می‌نویسد.
• ${\displaystyle g_1}$
  و ${\displaystyle g_2}$
  را به عنوان فایل‌های ورودی و ${\displaystyle f_1}$
  و ${\displaystyle f_2}$
  را به عنوان فایل‌های خروجی در نظر می‌گیرد و مراحل بالا را تکرار می‌کند.

${\displaystyle \leftarrow }$

مرتب‌سازی چندفازه همان مرتب‌سازی ادغامی است که به جای استفاده از چهار فایل کمکی، از سه فایل کمکی استفاده می‌کند که مراحل آن به شرح ذیل است:

1. به فایل ورودی کم‌ترین تعداد رکورد را با کلید ${\displaystyle \mathrm{\infty }}$
   اضافه می‌کند تا طول آن n برابر iامین عدد فیبوناچی_ ${\displaystyle F_i}$
   _ شود.
2. فایل ورودی را به دو فایل با اندازه‌های ${\displaystyle F_{i-1}}$
   و ${\displaystyle F_{i-2}}$
   تقسیم می‌کند_ ${\displaystyle F_i=F_{i-1}+F_{i-2}}$
   _.
3. قدم‌ای زیر را به تعداد M بار تکرار می‌کند:

• فرض می‌کند ${\displaystyle f_1}$
  دارای ${\displaystyle F_m}$
  قطعهٔ مرتب‌شده‌است_ در ابتدای کار ${\displaystyle F_m=F_i}$
  _ که اندازهٔ هر قطعهٔ آن ${\displaystyle F_r}$
  است_ در ابتدای کار ${\displaystyle F_r=F_0=1}$
  _. همچنین ${\displaystyle f_2}$
  دارای ${\displaystyle F_{m+1}}$
  قطعهٔ مرتب‌شده‌است که اندازهٔ هر قطعهٔ آن ${\displaystyle F_{r+1}}$
  است و ${\displaystyle f_3}$
  خالی است.
• ${\displaystyle F_m}$
  قطعهٔ مرتب از فایل ${\displaystyle f_1}$
  را با همین تعداد قطعهٔ مرتب از فایل ${\displaystyle f_2}$
  در هم ادغام کرده و حاصل را در ${\displaystyle f_3}$
  می‌نویسد.
• حال ${\displaystyle f_1}$
  خالی، ${\displaystyle f_2}$
  دارای ${\displaystyle F_{m-1}=F_{m+1}-F_m}$
  قطعه مرتب به اندازهٔ ${\displaystyle F_{r+2}=F_r+F_{r+1}}$
  است.
• نام‌گذاری فایل‌ها را به تناسب تغییر می‌دهد.

جدول زیر نشان‌دهنده چند مرحله از الگوریتم بالا است:

محمد فراهانی مهر

• قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها، چاپ دوم، انتشارات فاطمی، ۱۳۸۹.
• ویکی‌پدیای انگلیسی