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

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

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

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

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

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

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

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

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

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

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

$f_{1}$ و $f_{2}$ را به عنوان فایل‌های ورودی در نظر می‌گیرد. هر بار، قطعات با شماره‌های یکسان $f_{1}$ و $f_{2}$ را با یکدیگر ادغام می‌کند. حاصل هر ادغام قطعه‌ای مرتب به طول $2^{i}$ است_ بجز قطعهٔ آخر که ممکن است طولش کمتر باشد_. این قطعات را یکبار در میان در $g_{1}$ و $g_{2}$ می‌نویسد.
$g_{1}$ و $g_{2}$ را به عنوان فایل‌های ورودی و $f_{1}$ و $f_{2}$ را به عنوان فایل‌های خروجی در نظر می‌گیرد و مراحل بالا را تکرار می‌کند.

$\leftarrow$ به وسیله استقرا می‌توان نشان داد که در انتهای مرحلهٔ iام هر فایل خروجی دارای قطعات مرتب و به طول $2^{i}$ است_ بجز حداکثر یک قطعه که طولش از این مقدار کمتر است_. همچنین، تعداد قطعه‌های دو فایل خروجی حداکثر یک واحد اختلاف دارند، بنابراین در انتهای مرحلهٔ $M=\lceil log(n)\rceil$ یکی از فایل‌های خروجی حاوی تنها یک قطعهٔ مرتب از تمام n زکورد فایل ورودی و دیگری خالی است. با توجه به این که در هر تکرار همهٔ n رکورد موجود یکبار خوانده و یکبار نوشته می‌شود، تعداد دست‌رسی‌ها به دیسک در مجموع برابر $2n(\lceil log(n)\rceil +1)$ است.

مرتب‌سازی خارجی چندفازه

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

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

فرض می‌کند $f_{1}$ دارای $F_{m}$ قطعهٔ مرتب‌شده‌است_ در ابتدای کار $F_{m}=F_{i}$ _ که اندازهٔ هر قطعهٔ آن $F_{r}$ است_ در ابتدای کار $F_{r}=F_{0}=1$ _. همچنین $f_{2}$ دارای $F_{m+1}$ قطعهٔ مرتب‌شده‌است که اندازهٔ هر قطعهٔ آن $F_{r+1}$ است و $f_{3}$ خالی است.
$F_{m}$ قطعهٔ مرتب از فایل $f_{1}$ را با همین تعداد قطعهٔ مرتب از فایل $f_{2}$ در هم ادغام کرده و حاصل را در $f_{3}$ می‌نویسد.
حال $f_{1}$ خالی، $f_{2}$ دارای $F_{m-1}=F_{m+1}-F_{m}$ قطعه مرتب به اندازهٔ $F_{r+2}=F_{r}+F_{r+1}$ است.
نام‌گذاری فایل‌ها را به تناسب تغییر می‌دهد.