مرتب سازی خارجی:
ساعت ٧:٢٠ ‎ب.ظ روز ۱۳۸٧/۱٢/٤  کلمات کلیدی:

به طور کلی الگوریتم‌‌های مرتب سازی به دو دسته داخلی(Internal )  و خارجی(External )  تقسیم‌بندی می‌شوند. در مرتب سازی داخلی تمامی محتویات لیست در حافظه اصلی جا شده و تمامی عملیات در حافظه انجام می‌پذیرد. ولی در مرتب سازی خارجی به علت بزرگی فایل نمی‌توان تمامی داده‌ها را به یکباره در حافظه جا داد. هنگامی که فایلی در حافظه جا نگیرد مرتب سازی آن به دو مرحله نیاز دارد. در مرحله اول فایل به چند بخش (segment ) تقسیم شده و هر بخش به صورت مجزا در حافظه مرتب می‌شوند. در مرحله دوم بخش‌های مرتب شده با هم ادغام (merge ) می‌شوند. هر مرحله حداقل به یکبار خواندن و یکبار نوشتن فایل نیاز دارند. بنابراین روشهای مرتب سازی با یک دیسک، حداقل به چهار بار زمان خواندن کل فایل نیاز دارند و این زمان بر زمانهای دیگر (نظیر مقایسه و جابجایی در حافظه) غلبه می‌کند. البته به کمک دو دیسک می‌توان عملیات خواندن و نوشتن را به صورت موازی انجام داد و زمان فوق را نصف کرد. در مرتب سازی خارجی هنگامی که فقط یک دیسک داریم، عموما از روش Heapsort  برای ساخت بخش‌های مرتب شده اولیه استفاده می‌کنیم. الگوریتم‌ Heapsort  بر خلاف بیشتر روشهای مرتب سازی دیگر، می‌تواند به صورت موازی با عملیات ورودی و خروجی دیسک اجرا شود. بدین ترتیب فقط زمان I/O در محاسبات وارد می‌شود. یعنی زمان مرتب سازی برابر زمان ورودی و خروجی خواهد بود. این ویژگی در روشهای دیگری مانند Bubblesort  و Quicksort  وجود دارند. در واقع Heapsort سریعترین روش برای تولید بخشهای مرتب شده با یک دیسک می‌باشد، و از آنجا که در مرتب سازی خارجی، فایل به صورت بخش بخش مرتب می‌شود، در انتها می‌بایست این بخشها با یکدیگر ادغام گردند.

¯ در مرتب سازی خارجی ظرفیت حافظه نقش مهمی دارد. اگر ظرفیت حافظه اصلی آنقدر بزرگ می‌بود که تمام فایل در آن جا می‌شد دیگر نیازی به این بحثها نبود. امروزه اغلب هزینه افزایش حافظه اصلی جهت بهبود کارایی الگوریتم‌های مرتب سازی خارجی، کمتر از هزینه استفاده از چند دیسک درایو می‌باشد.

¯ یک ویژگی مهم الگوریتم Heapsort آن است که همه اعمال ‌I/O ترتیبی می‌باشند. یعنی تمام رکوردها به ترتیبی که در فایل قرار دارند خوانده شده و تمام رکوردها به صورت مرتب شده چاپ می‌شوند. بنابراین این روش را هم برای دیسک و هم برای نوار می‌توان به کار ‌برد. از طرف دیگر چون همه عملیات I/O  ترتیبی است، این کار با حداقل زمان استوانه‌جویی انجام می‌پذیرد.