مرتب سازی خارجی ( به انگلیسی: External Sorting ) اصطلاحی است که به دسته ای از الگوریتم های مرتب سازی که برای مرتب کردن مقادیر بزرگ داده به کار می روند گفته می شود. مرتب سازی خارجی زمانی به کار می رود که محدودیت در حافظه اصلی ( عموماً RAM ) وجود دارد و درعوض داده به جای این که روی RAM قرار بگیرد روی حافظه ای خارجی و کندتر قرار داشته باشد ( مثلاً روی Hard drive ) . مرتب سازی خارجی معمولاً از استراتژی مرتب سازی ادغامی استفاده می کند. در فرایند مرتب سازی تکه های به اندازه کافی کوچک داده که در حافظه اصلی ( RAM ) جا می گیرند، از فایل مورد نظر خوانده شده، مرتب سازی شده و در یک فایل کمکی نوشته و ذخیره می شوند. در مرحله ادغام، تکه فایل های ذخیره شده با هم ترکیب می شوند و یک فایل بزرگ و واحد و در عین حال مرتب شده را می سازند. در این حالت زمان دست رسی به یک بلوک اطلاعات بر روی حافظه جانبی و خواندن آن ها در حافظهٔ اصلی، هزاران برابر بیشتر از زمان دسترسی به حافظهٔ اصلی است، بنابراین معیار سنجش کارایی الگوریتم های خارجی را تعداد دسترسی ها به حافظهٔ خارجی - دیسک - در نظر می گیریم، همچنین زمان پردازش مورد نیاز پس از هر خواندن از حافظه جانبی، یک مقدار ثابت در نظر گرفته می شود، چون اندازه میان گیری که در حافظه اصلی، این داده را در خود ذخیره می کند، مستقل از اندازهٔ داده است و ثابت فرض می شود.
در الگوریتم مرتب سازی خارجی فرض می کنیم:
• اطلاعات بر روی فایل های حافظهٔ خارجی به صورت ترتیبی ذخیره شده است: یعنی برای خواندن رکورد mام باید m - 1رکورد قبلی آن خوانده شود.
• هر فایل شامل n رکورد است و هر رکورد یک کلید یکتا دارد.
• هدف ایجاد فایلی است که رکوردهای آن بر اساس کلیدشان مرتب باشند.
• با هر دسترسی به دیسک، یک بلوک به اندازهٔ k رکورد خوانده می شود.
• تعداد فایل هایی که در یک زمان می توانند باز باشند حداکثر برابر مقدار ثابت r است.
• اندازه حافظه اصلی قابل استفاده - یا همان میان گیرها - از مرتبه O ( 1 ) {\displaystyle O ( 1 ) } است.
• عملیات مقایسه و محاسبات دیگر فقط در حافظهٔ اصلی انجام می شود.
الگوریتم مرتب سازی ادغامی خارجی مثالی از مرتب سازی خارجی می باشد، که تکه های داده را که در RAM قرار می گیرند مرتب سازی می کند، سپس تکه هایی که مرتب شده اند را با هم ادغام می کند. به طور مثال برای مرتب کردن یک فایل با حجم 900MB، فقط 100MB حافظه RAM در اختیار داریم، به صورت زیر عمل می کنیم:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر الگوریتم مرتب سازی خارجی فرض می کنیم:
• اطلاعات بر روی فایل های حافظهٔ خارجی به صورت ترتیبی ذخیره شده است: یعنی برای خواندن رکورد mام باید m - 1رکورد قبلی آن خوانده شود.
• هر فایل شامل n رکورد است و هر رکورد یک کلید یکتا دارد.
• هدف ایجاد فایلی است که رکوردهای آن بر اساس کلیدشان مرتب باشند.
• با هر دسترسی به دیسک، یک بلوک به اندازهٔ k رکورد خوانده می شود.
• تعداد فایل هایی که در یک زمان می توانند باز باشند حداکثر برابر مقدار ثابت r است.
• اندازه حافظه اصلی قابل استفاده - یا همان میان گیرها - از مرتبه O ( 1 ) {\displaystyle O ( 1 ) } است.
• عملیات مقایسه و محاسبات دیگر فقط در حافظهٔ اصلی انجام می شود.
الگوریتم مرتب سازی ادغامی خارجی مثالی از مرتب سازی خارجی می باشد، که تکه های داده را که در RAM قرار می گیرند مرتب سازی می کند، سپس تکه هایی که مرتب شده اند را با هم ادغام می کند. به طور مثال برای مرتب کردن یک فایل با حجم 900MB، فقط 100MB حافظه RAM در اختیار داریم، به صورت زیر عمل می کنیم:
wiki: مرتب سازی خارجی