مرتب‌سازی ادغامی چندمرحله‌ای - ویکی‌پدیا، دانشنامهٔ آزاد

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه، محتوای آن را بهبود بخشید.

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

مرتب‌سازی ادغامی مجموعه‌ای از داده را به تکه‌هایی مرتب تجزیه می‌کند و سپس بارها و بارها تکه‌ها را ادغام می‌کند تا تنها یک تکه، مجموعه‌ای مرتب شده، باقی بماند.

مرتب‌سازی ادغامی عادی از چهار فایل استفاده می‌کند و آن‌ها را به صورت یک دسته فایل‌های ورودی و یک دسته فایل‌های خروجی سازمان‌دهی می‌کند. مجموعهٔ داده‌ها به‌طور مساوی بین دو فایل توزیع شده، یا به عنوان تکهٔ مرتب‌شده یا در ساده‌ترین حالت، یک داده مفرد که می‌توان آن را یک تکه مرتب‌شده با اندازه ۱ در نظر گرفت. هنگامی که همهٔ مجموعهٔ داده‌ها به دو فایل منتقل می‌شوند، این دو فایل به فایل‌های ورودی برای اولین ادغام تبدیل می‌شوند. در هر بار ادغام، دو فایل ورودی ادغام می‌شوند، خروجی‌ها به صورت متناوب بین دو فایل خروجی توزیع، و دوباره به‌طور مساوی بین دو فایل خروجی اجرا می‌شود (تا آخرین مرحلهٔ ادغام). هنگامی که تمام تکه‌ها از دو فایل ورودی با هم ادغام شدند و خروجی حاصل شد، برای ادغام بعدی فایل‌های خروجی به فایل‌های ورودی تبدیل شده و بالعکس. در هر مرحله تعداد تکه‌ها به نصف کاهش می‌یابد، مانند ۶۴٬۳۲٬۱۶٬۸٬۴٬۲٬۱. در آخرین مرحلهٔ ادغام، هر کدام از دو فایل ورودی تنها یک تکه مرتب شده دارند (نصف مجموعه‌ای از داده‌ها)، و نتیجهٔ ادغام، یک تکهٔ مرتب شده (مجموعه دادهٔ طبقه‌بندی شده) در یکی از فایل‌های خروجی است. این روش در مرتب‌سازی ادغامی با استفاده از درایوهای نواری نیز توصیف شده‌است.

اگر تنها سه فایل وجود داشت، مرتب‌سازی ادغامی دو فایل مرتب‌شده را در یک فایل ادغام کرده، سپس تکه را به‌طور مساوی بین دو فایل خروجی توزیع می‌کند. در نتیجه در هر تکرار تعداد تکه‌ها به نصف کاهش می‌یابد، توزیع مجدد تعداد تکه‌ها را کاهش نمی‌دهد (اندازهٔ عامل یک است). تعداد کاهش تکه‌ها در هر تکرار را می‌توان به اندازه جذر۲ در نظر گرفت. اگر ۵ فایل وجود داشت، الگوی ادغام به تناوب بین ادغام ۳ راهه و ادغام ۲ راهه اجرا می‌شود که به‌طور متوسط عامل کاهش جذر ۶≈۲٫۴۵. به‌طور کلی، برای هر تعداد فایل زوج، هر مرحله از مرتب کردن بر اساس مرتب‌سازی ادغامی عادی تعداد تکه‌ها را به نصف کاهش می‌دهد، یا برای تعداد فرد فایل O، در هر تکرار از مرتب کردن بر اساس مرتب‌سازی ادغامی عادی تعداد تکه‌ها به جذر ((O² - 1)/4) کاهش می‌باید.

برای Nهای کمتر از ۸ فایل، ادغام چند مرحله‌ای به علت توزیع نایکنواخت تکه‌های مرتب شده بین 1-N فایل به ضریب کاهش مؤثر تعداد تکهٔ بیشتری می‌رسد (توضیح داده شده در بخش بعدی). در هر مرحله تکه‌ها از 1-N فایل بر روی یک تک فایل خروجی ادغام می‌شوند. هنگامی که به انتهای یکی از 1-N فایل برسیم، آن فایل به فایل خروجی جدید بدل می‌شود و اگر فایل خروجی باشد به یکی از 1-N فایل ورودی تبدیل و مرحلهٔ جدیدی از مرتب‌سازی ادغامی چند مرحله‌ای آغاز می‌شود. هر مرحله تنها کسری از مجموعهٔ داده (حدود ۱/۲ تا ۳/۴)، به جز آخرین مرحله که تمام مجموعه داده را به یک تکهٔ مرتب شده تبدیل می‌کند، ادغام می‌شود. توزیع اولیه به نحوی اجرا می‌شود که تنها یک فایل ورودی در یک زمان خالی بماند، به جز مرحله نهایی که 1-N تکه منفرد (در اندازه‌های مختلف، بعدتر توضیح داده خواهد شد) از 1-N فایل ورودی به یک فایل خروجی ادغام می‌شوند و نتیجه یک تکه مرتب شده‌است که همان مجموعه دادهٔ مرتب شده‌است.

برای هر مرحله، تعداد کل تکه‌ها از الگویی مشابه به سری معکوس اعداد فیبوناچی از مرتبه بالاتر پیروی می‌کند. در ۴ فایل، و یک مجموعه داده شامل ۵۷ تکه، تعداد تکه‌ها در هر تکرار ۵۷ ،۳۱ ،۱۷ ،۹ ،۵ ،۳ ،۱ می‌شود.^[۱][۲] توجه داشته باشید که به جز آخرین مرحله، عامل کاهش تعداد تکه‌ها کمی کمتر از ۲، در حدود ۱٫۸۴ برای یک مورد دارای ۴ فایل می‌باشد. اما در هر مرحله به جز آخرین کاهش، تعداد تکه‌های در حال پردازش در حدود ۶۵ درصد از مجموعه دادهٔ اولیه است، به‌طوری‌که عامل کاهش تعداد تکه‌ها در هر مجموعه داده در حال پردازش در طول مراحل به‌طور متوسط برابر ۲٫۸۳ = ۰٫۶۵ / ۱٫۸۴ است. برای یک مجموعه داده شامل ۵۷ تکه از هر ۱ ورودی، پس از توزیع اولیه، مرتب‌سازی ادغامی چند مرحله‌ای با حرکت ۲۳۲ پرونده در طول ۶ تکرار برای مرتب کردن داده‌ها طول می‌کشد، که به‌طورکلی عامل کاهش ۲٫۷۰ دارد (در بعد به توضیح با جزئیات بیشتر پرداخته می‌شود). پس از اولین تکرار چند مرحله‌ای، فایل خروجی در حال حاضر شامل نتایج حاصل از ادغام 1-N تکهٔ اصلی می‌شود، اما باقی‌مانده 2-N فایل ورودی هنوز هم حاوی تکه‌های اصلی هستند، به‌طوری‌که در ادغام دوم تکه‌هایی از اندازه (3 - N -1) + (N-۲) = (2N) از تکه‌های اصلی تولید می‌شود. در تکرار سوم، تکه‌هایی از اندازه (7-4N) تولید می‌کند. با ۴ فایل، مرحله اول تکه‌هایی از اندازه ۳ تکهٔ اصلی ایجاد می‌شود، مرحله دوم تکه‌هایی از اندازه ۵ تکهٔ اصلی، مرحله سوم تکه‌هایی از اندازه ۹ تکهٔ اصلی و به همین روال که از الگوی فیبوناچی ۵۷ ،۳۱ ،۱۷ ،۹ ،۵ ،۳ ،۱، …، در افزایش در اندازه تکه از این الگو پیروی می‌کند و به عنوان کاهش در تعداد تکه‌ها در جهت معکوس نیز هست. به‌طور مثال در ۴ فایل و ۵۷ تکه از هر یک ورودی، آخرین مرحله ادغام ۳ تکه از اندازه‌های ۹ ،۱۷ ،۳۱ ادغام شده‌اند و تنها یک تکه از اندازهٔ ۳۱+۱۷+۹=۵۷ به صورت مرتب‌شده باقی می‌ماند. یک مثال از تعداد تکه و اندازهٔ تکه‌ها برای ۴ فایل، ۳۱ ورودی را می‌توان در جدول ۴٫۳ مشاهده کرد.^[۳]

ساده‌ترین راه برای مشاهده روند مرتب‌سازی ادغامی چند مرحله‌ای شروع از شرایط پایان آن و به صورت بالعکس است. در شروع هر تکرار٫ دو فایل ورودی و یک فایل خروجی وجود خواهد داشت٫ در پایان تکرار یکی از فایل‌های ورودی به‌طور کامل مصرف شده و تبدیل به فایل خروجی برای تکرار در مرحله بعد می‌شود. فایل خروجی فعلی در مرحلهٔ بعد تبدیل به فایل ورودی برای تکرار خواهد شد. فایل‌های باقی‌مانده (فقط یکی از ۳ فایل) تنها بخشی از آن استفاده می‌شود و باقی‌مانده تبدیل به ورودی برای مرحلهٔ بعد می‌شود.

فایل اول خالی شده و به عنوان فایل خروجی در نظر گرفته می‌شود. یک تکه در هر نوار ورودی باقی می‌ماند و از ادغام این تکه‌ها باهم فایل مرتب‌شده حاصل می‌شود.

فایل ۱ (خروجی): <یک تکه> * (فایل مرتب‌شده) فایل ۲ (ورودی): ...| <یک تکه> * -> … <یک تکه> * (مصرف‌شده) فایل ۳ (ورودی): | <یک تکه> * <یک تکه> * (مصرف‌شده) ... تکه‌های ممکن در حال حاضر خوانده شده‌اند | نشانگر فایل خوان را علامت‌گذاری می‌کند * پایان فایل را علامت‌گذاری می‌کند 

به مرحلهٔ قبل برمی‌گردیم٫ما از فایل‌های ۱و۲ می‌خواندیم. یک تکه از یک و دو، قبل از اینکه فایل اول خالی شود، ادغام شده‌است. توجه داشته باشید که فایل دوم به‌طور کامل مصرف نشده است، یک تکه برای ادغام در آخرین ادغام باقی مانده‌است (شکل بالا).

فایل ۱ (ورودی): ...| <یک تکه> * … <یک تکه> * فایل ۲ (ورودی): | <دو تکه> * -> <یک تکه> | <یک تکه> * فایل ۳ (خروجی): <یک تکه> * 

یک مرحله دیگر به عقب بازگشته٫ دو تکه از فایل‌های یک و سه قبل از اینکه فایل سوم خالی شود ادغام شده‌اند.

فایل ۱ (ورودی): | <سه تکه> * … <دو تکه> | <یک تکه> * فایل ۲ (خروجی): -> <دو تکه> * فایل ۳ (ورودی): ...| <پنج تکه> * <سه تکه> | <دو تکه> * 

یک مرحله دیگر به عقب بازگشته٫ سه تکه از فایل‌های دو و سه قبل از اینکه فایل اول خالی شود ادغام شده‌اند.

فایل ۱ (خروجی): … <سه تکه> * فایل ۲ (ورودی): ...| <سه تکه> * -> … <سه تکه> * فایل ۳ (ورودی): | <پنج تکه> * <سه تکه> | <دو تکه> * 

یک مرحله دیگر به عقب بازگشته٫ پنج تکه از فایل‌های یک و دو قبل از اینکه فایل اول خالی شود ادغام شده‌اند.

فایل ۱ (ورودی): ...| <پنج تکه> * … <پنج تکه> * فایل ۲ (ورودی): | <هشت تکه> * -> <پنج تکه> | <سه تکه> * فایل ۳ (خروجی): <پنج تکه> * 

به مرتب‌سازی ادغامی چند مرحله‌ای بدون نقص برای ۳ فایل نگاه کنید، تعداد تکه‌ها برای ادغام به صورت بالعکس از دنبالهٔ فیبوناچی پیروی می‌کند. این روند برای بیشتر از سه فایل کمی پیچیده‌تر است؛ برای ۴ فایل، با شروع از حالت آخر و به صورت بالعکس، الگو تعداد تکه‌ها مطابق {۱٬۰٬۰٬۰}, {۰٬۱٬۱٬۱}, {۱٬۰٬۲٬۲}, {۳٬۲٬۰٬۴}, {۷٬۶٬۴٬۰}, … است. برای اینکه همه چیز بهینه کار کند، در آخرین فاز ادغام هر فایل ورودی باید دقیقاً یک تکه داشته‌باشد، اگر هرکدام از فایل‌های ورودی از یک تکه بیشتر داشته‌باشند یک فاز دیگر نیاز خواهدبود، در نتیجه، مرتب‌سازی ادغامی چند مرحله‌ای نیاز دارد تا از نحوهٔ توزیع اولیهٔ داده‌ها در تکه‌های ورودی تا تکه‌های خروجی آگاه باشد. برای مثال یک فایل ورودی با ۱۳ تکه، ۵ تکه را در فایل اول و ۸ تکه را در فایل دوم می‌نویسد. در عمل فایل ورودی تعداد مورد نیاز تکه برای توزیع بی‌نقص را ندارد. مرتب‌سازی ادغامی چند مرحله‌ای این اختلاف را با پیمایش روی توزیع حقیقی با انگاشت «تکه‌های ساختگی»[۱] مرتفع می‌کند و توزیع تکه‌های ایده‌آل را شبیه‌سازی می‌کند.^[۴] یک تکه ساختگی همانند یک تکهٔ بدون داده رفتار می‌کند. ادغام روی یک یا چند تکهٔ ساختگی با یک یا چند تکهٔ حقیقی همانند آن است که فقط روی تکه‌های حقیقی ادغام صورت گرفته‌باشد.

بعد از توزیع اولیه، مرتب‌سازی ادغامی عادی که با ۴ فایل کار می‌کند، ۱۶ تک دادهٔ ضبط شده را در ۴ سطر در کل مجموعه داده مرتب می‌کند به‌طوری‌که در مجموع ۶۴ دادهٔ ضبط شده در راستای مرتب‌سازی مجموعه داده بعد از توزیع اولیه جابه‌جا می‌شوند. یک مرتب‌سازی ادغامی چند مرحله‌ای که از ۴ فایل استفاده می‌کند ۱۷ تک دادهٔ ضبط شده را در ۴ سطر مرتب می‌کند، اما از آنجایی که به ازای هر سطر در آخرین مرحله، کسری از داده‌های مجموعه داده جابه‌جا می‌شود در مجموع تنها ۴۸ دادهٔ ضبط شده در راستای مرتب‌سازی مجموعه داده بعد از توزیع اولیه جابه‌جا می‌شوند. در این مورد ضریب عمل کرد مرتب‌سازی ادغامی معمولی برابر ۲٫۰ است در حالی که ضریب عمل کرد سراسری چندمرحله‌ای تقریباً برابر ۲٫۷۳ است. برای توضیح دادن چگونگی ارتباط بین ضریب کاهش عملکرد و بازدهی الگوریتم مرتب‌سازی از معادلات ضریب کاهش عملکرد که در ذیل آمده بهره می‌بریم:

ضریب کاهش = exp(تعداد تکه‌ها*log(تعداد تکه‌ها)/تعداد جابه‌جایی تکه‌ها) تعداد جابه‌جایی تکه‌ها = تعداد تکه‌ها*log(تعداد تکه‌ها)/log(ضریب کاهش) تعداد جابه‌جایی تکه‌ها = تعداد تکه‌ها*log(ضریب کاهش)(تعداد تکه‌ها)

از معادلهٔ تعداد جابه‌جایی تکه‌ها در مثال زیر استفاده می‌کنیم. مرتب‌سازی ادغامی معمول ---> ۶۴ = ۱۶ * (16)log2 مرتب‌سازی ادغامی چندمرحله‌ای ---> ۴۸ = ۱۷ * (17)log2.۷۳

در ادامه جدولی از ضریب کاهش عملکرد مؤثر برای مرتب‌سازی ادغامی چند مرحله‌ای و معمولی آورده شده که بر اساس تعداد فایل‌های لیست شده‌است و مبتنی بر مرتب‌سازی حقیقی چند میلیون دادهٔ ذخیره شده‌است. این جدول تقریباً با جداول منتقل شده ضریب کاهش عملکرد به ازای هر مجموعه داده که در شکل ۳ و ۴ در پروندهٔ polyphase merge sort.pdf نشان داده شده، مطابقت دارد.

# فایل‌ها | متوسط تعداد تکه‌های داده در هر بار تکرار | | ضریب کاهش چندمرحله‌ای با تعداد ایده‌آلی داده | | | ضریب کاهش مرتب‌سازی ادغامی معمولی با تعداد ایده‌آلی داده | | | | ۳ .۷۳ ۱٫۹۴ ۱٫۴۱ (جذر ۲) ۴ .۶۳ ۲٫۶۸ ۲٫۰۰ ۵ .۵۸ ۳٫۲۰ ۲٫۴۵ (جذر ۶) ۶ .۵۶ ۳٫۵۶ ۳٫۰۰ ۷ .۵۵ ۳٫۸۰ ۳٫۴۶ (جذر ۱۲) ۸ .۵۴ ۳٫۹۵ ۴٫۰۰ ۹ .۵۳ ۴٫۰۷ ۴٫۴۷ (جذر ۲۰) ۱۰ .۵۳ ۴٫۱۵ ۵٫۰۰ ۱۱ .۵۳ ۴٫۲۲ ۵٫۴۸ (جذر ۳۰) ۱۲ .۵۳ ۴٫۲۸ ۶٫۰۰ ۳۲ .۵۳ ۴٫۸۷ ۱۶٫۰۰ 

در مجموع، مرتب‌سازی ادغامی چند مرحله‌ای از مرتب‌سازی ادغامی معمولی زمانی بهتر است که کمتر از ۸ فایل موجود باشد و این در حالی است که مرتب‌سازی ادغامی معمولی در حوالی ۸ یا تعداد بیشتری فایل شروع به پیشی گرفتن از مرتب‌سازی ادغامی چند مرحله‌ای می‌کند.^[۵][۶]

• Bradley, James (1982), File and Data Base Techniques, Holt, Rinehart and Winston, ISBN 0-03-058673-9
• Reynolds, Samuel W. (August 1961), "A generalized polyphase merge algorithm", Communications of the ACM, New York, NY: ACM, 4 (8): 347–349, doi:10.1145/366678.366689
• Sedgewick, Robert (1983), Algorithms, Addison-Wesley, pp. 163–165, ISBN 0-201-06672-6