موضوع مقاله: مرتب‌سازی خارجی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی خارجی | مقدمه: مرتب‌سازی خارجی زمانی به کار می‌رود که محدودیت در حافظه اصلی (عموماً RAM) وجود دارد و درعوض داده به جای این که روی RAM قرار بگیرد روی حافظه‌ای خارجی و کندتر قرار داشته باشد (مثلاً روی Hard drive). | ## بخش 1: مرتب‌سازی خارجی | در فرایند مرتب‌سازی تکه‌های به اندازه کافی کوچک داده که در حافظه اصلی (RAM) جا می‌گیرند، از فایل مورد نظر خوانده شده، مرتب‌سازی شده و در یک فایل کمکی نوشته و ذخیره می‌شوند. در مرحله ادغام، تکه فایل‌های ذخیره شده با هم ترکیب می‌شوند و یک فایل بزرگ و واحد و در عین حال مرتب شده را می‌سازند. در این حالت زمان دست‌رسی به یک بلوک اطلاعات بر روی حافظه جانبی و خواندن آن‌ها در حافظهٔ اصلی، هزاران برابر بیشتر از زمان دسترسی به حافظهٔ اصلی است، بنابراین معیار سنجش کارایی الگوریتم‌های خارجی را تعداد دسترسی‌ها به حافظهٔ خارجی- دیسک- در نظر می‌گیریم، همچنین زمان پردازش مورد نیاز پس از هر خواندن از حافظه جانبی، یک مقدار ثابت در نظر گرفته می‌شود، چون اندازه میان‌گیری که در حافظه اصلی، این داده را در خود ذخیره می‌کند، مستقل از اندازهٔ داده‌است و ثابت فرض می‌شود. فرضیات الگوریتم مرتب‌سازی خارجی در الگوریتم مرتب‌سازی خارجی فرض می‌کنیم: اطلاعات بر روی فایل‌های حافظهٔ خارجی به صورت ترتیبی ذخیره شده‌است: یعنی برای خواندن رکورد mام باید m-1رکورد قبلی آن خوانده شود. تعداد فایل‌هایی که در یک زمان می‌توانند باز باشند حداکثر برابر مقدار ثابت r است. مرتب‌سازی ادغامی خارجی الگوریتم مرتب‌سازی ادغامی خارجی مثالی از مرتب‌سازی خارجی می‌باشد، که تکه‌های داده را که در RAM قرار می‌گیرند مرتب‌سازی می‌کند، سپس تکه‌هایی که مرتب شده‌اند را با هم ادغام می‌کند. به‌طور مثال برای مرتب کردن یک فایل با حجم 900MB، فقط 100MB حافظه RAM در اختیار داریم، به صورت زیر عمل می‌کنیم: 100MB از داده را خوانده و روی RAM قرار می‌دهیم و توسط یکی از متدهای مرتب‌سازی مثل مرتب‌سازی سریع آنرا مرتب می‌کنیم. | ## بخش 2: مرتب‌سازی خارجی | این دو مرحله را برای تمام تکه‌های ۱۰۰ مگابایتی که در مراحل بعد می‌خوانیم، انجام می‌دهیم، حالا باید تکه‌های مرتب‌شده را ادغام کنیم تا یک فایل خروجی واحد داشته باشیم. 10MB اول هر فایل مرتب‌شده را در بافر ورودی در RAM می‌ریزیم (۹ فایل با حجم 10MB) و 10MB باقی‌مانده را به بافر خروجی اختصاص می‌دهیم_در عمل اگر بافر خروجی را بزرگتر و بافر ورودی را کمی کوچکتر در نظر بگیریم ممکن است عملکرد بهتری داشته باشیم. اگر بافر خروجی پر شد، آنرا در فایل نهایی ذخیره می‌کنیم و بافر خروجی را خالی می‌کنیم. اگر هر کدام از ۹ بافر ورودی خالی شدند آنرا با 10MB بعدی از فایل 100MB مربوطه پر می‌کنیم تا زمانی که کل فایل ۱۰۰ مگابایتی تمام شود. این گامی کلیدی است که باعث می‌شود ادغام خارجی به درستی کار کند، چرا که الگوریتم ادغام معمولی، یکباره تکه فایل را می‌خواند در حالیکه هر تکه نباید به‌طور کامل بارگزاری شود، بلکه قسمت‌های پشت سرهم از آن تکه، آن هم در صورت نیاز باید بارگزاری شوند. الگوریتم کلی مرتب‌سازی ادغامی خارجی الگوریتم به صورت زیر عمل می‌کند: فایل ورودی را به دو فایل و با حداکثر یک رکورد اختلاف تقسیم می‌کند. حاصل هر ادغام قطعه‌ای مرتب به طول است_ بجز قطعهٔ آخر که ممکن است طولش کمتر باشد_. | ## بخش 3: مرتب‌سازی خارجی | و را به عنوان فایل‌های ورودی و و را به عنوان فایل‌های خروجی در نظر می‌گیرد و مراحل بالا را تکرار می‌کند. به وسیله استقرا می‌توان نشان داد که در انتهای مرحلهٔ iام هر فایل خروجی دارای قطعات مرتب و به طول است_ بجز حداکثر یک قطعه که طولش از این مقدار کمتر است_. همچنین، تعداد قطعه‌های دو فایل خروجی حداکثر یک واحد اختلاف دارند، بنابراین در انتهای مرحلهٔ یکی از فایل‌های خروجی حاوی تنها یک قطعهٔ مرتب از تمام n زکورد فایل ورودی و دیگری خالی است. با توجه به این که در هر تکرار همهٔ n رکورد موجود یکبار خوانده و یکبار نوشته می‌شود، تعداد دست‌رسی‌ها به دیسک در مجموع برابر است. مرتب‌سازی خارجی چندفازه مرتب‌سازی چندفازه همان مرتب‌سازی ادغامی است که به جای استفاده از چهار فایل کمکی، از سه فایل کمکی استفاده می‌کند که مراحل آن به شرح ذیل است: به فایل ورودی کم‌ترین تعداد رکورد را با کلید اضافه می‌کند تا طول آن n برابر iامین عدد فیبوناچی_ _ شود. قدم‌ای زیر را به تعداد M بار تکرار می‌کند: فرض می‌کند دارای قطعهٔ مرتب‌شده‌است_ در ابتدای کار _ که اندازهٔ هر قطعهٔ آن است_ در ابتدای کار _. قطعهٔ مرتب از فایل را با همین تعداد قطعهٔ مرتب از فایل در هم ادغام کرده و حاصل را در می‌نویسد. | ## جمع‌بندی | جدول زیر نشان‌دهنده چند مرحله از الگوریتم بالا است: پس از گام ابتدا - ۱ - ۲ - ۳ - … … … ...