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

یک الگوریتم مرتب‌سازی مقایسه‌ای در علوم ریاضی و کامپیوتر

در علوم رایانه، مرتب‌سازی ادغام-درج یا الگوریتم فورد-جانسون از الگوریتم‌های مرتب‌سازی مقایسه‌ای است که در سال ۱۹۵۹ توسط لستر رادولف فورد و سلمر مارتین جانسون منتشر شد. این الگوریتم از الگوریتم‌های شناخته شده قبلی همچون مرتب‌سازی درجی دودویی و مرتب‌سازی ادغامی در بدترین حالت، از تعداد مقایسه‌های کمتری استفاده می‌کند.

مشخص است که کم بودن تعداد مقایسه‌ها معیاری مناسب برای اثربخشی یک الگوریتم مرتب‌سازی نیست؛ امّا از دیدگاه نظری کمینه کردن تعداد مقایسه‌ها در مسائل مرتب‌سازی همواره مهم بوده‌است.[۱] همین الگوریتم توسط ریاضیدان لهستانی به‌طور مستقل کشف شد.

مقدمه ای بر الگوریتم

ویرایش

فرض می‌کنیم ۵ عدد داریم ( )، آن‌ها را به سه دسته تقسیم می‌کنیم:  

سپس دو عدد موجود در دسته‌های دوتایی را باهم مقایسه می‌کنیم و بعد از آن دو عدد بزرگتر هر دسته را با یکدیگر مقایسه می‌کنیم. فرض می‌کنیم  . آنگاه باید دو عدد   را با هم مقایسه کنیم. در شکل‌های زیر جهت پیکان از عدد کوچکتر به سمت عدد بزرگتر است.

 
 

با توجه به شکل بالا داریم  . اکنون باید عنصر   را بین این سه عنصر مرتب شده درج کنیم که با دو مقایسه امکان‌پذیر است. (مرتب‌سازی درجی دودویی) سپس بعد از معلوم شدن جایگاه  ، عنصر   را در صف مرتب شده درج می‌کنیم که آن نیز با دو مقایسه امکان‌پذیر است.

الگوریتم

ویرایش

الگوریتم فورد-جانسون یا مرتب‌سازی ادغام-درج تعمیم جالبی از مقدمه بالاست. مراحل این الگوریتم به شرح زیر است:[۱][۲][۳]

ادغام

ویرایش
  1.   عنصر موجود را به   گروه دوتایی تقسیم می‌کنیم؛ و اگر   فرد بود، یک عنصر جفت نشده باقی می‌ماند.
  2.  مقایسه انجام می‌دهیم تا عنصر بزرگتر در هر گروه را بیابیم.
  3.   عنصر بزرگتر را به شکل بازگشتی مرتب می‌کنیم. حال عناصر مرتب شده را زنجیره اصلی می‌نامیم که به صورت  در شکل نمایش داده شده‌است.
     
  4. سپس با توجه به این که زنجیره اصلی مرتب شده‌است و عنصر   کوچکترین عنصر زنجیره است و می‌دانیم   از آن کوچکتر است، بنابراین می‌توان   را در ابتدای زنجیره درج نمود.
  5. بقیه عناصر که به شکل   نشان داده شده‌است را در زنجیره اصلی درج می‌کنیم. (با استفاده از مرتب‌سازی درجی)

روش درج کردن  ها به ترتیب زیر است:

 

 

سپس در آخر در صورت وجود،   را در زنجیره اصلی درج می‌نماییم.[۴]

تحلیل الگوریتم

ویرایش

برای بررسی تعداد مقایسه‌ها ابتدا به مقادیر  ها می‌پردازیم. این مقادیر باید باید به گونه‌ای باشند که تعداد عناصر زنجیره اصلی هنگام درج یک عنصر در مرحله  ام برابر  باشد.

در نتیجه داریم:

 

با حل رابطه بازگشتی بالا به جواب زیر می‌رسیم:

 

 را تعداد مقایسه‌های الگوریتم فورد-جانسون برای  عنصر می‌گیریم. ابتدا  مقایسه برای پیدا کردن عنصر بزرگتر در هر دسته داریم و سپس زنجیره اصلی را به شکل بازگشتی مرتب می‌کنیم و  هم تعداد مقایسه‌ها برای درج عناصر کوچکتر دسته‌ها در زنجیره اصلی است.

 

و برای هر  ، برابر است با  .

 

 

پس از تعریف  به شکل بالا می‌توان ثابت کرد :  

و شرط بالا معادل است با :  

بنابرابن داریم :  

در نتیجه:  

مقایسه با سایر الگوریتم‌ها

ویرایش

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

تعداد مقایسه‌های این الگوریتم مرتب‌سازی برای  برابر با کران پایین تعداد مقایسه‌های مرتب‌سازی‌های مقایسه‌ای است. این کران پایین برابر است با  

امّا تعداد مقایسه برای  های بزرگتر بیشتر از این کران پایین است.

همان‌طور که در جدول زیر دیده می‌شود، تعداد مقایسه‌ها در الگوریتم فورد-جانسون از دو الگوریتم ادغامی و درجی برای  های کوچکتر از   کمتر است.[۱]

تعداد مقایسه‌ها در بدترین حالت
۱۷ ۱۶ ۱۵ ۱۴ ۱۳ ۱۲ ۱۱ ۱۰ ۹ ۸ ۷ ۶ ۵ ۴ ۳ ۲ ۱ n
۵۴ ۴۹ ۴۵ ۴۱ ۳۷ ۳۳ ۲۹ ۲۵ ۲۱ ۱۷ ۱۴ ۱۱ ۸ ۵ ۳ ۱ ۰ مرتب‌سازی درجی
۶۵ ۴۹ ۴۵ ۴۱ ۳۸ ۳۳ ۳۰ ۲۷ ۲۵ ۱۷ ۱۴ ۱۱ ۹ ۵ ۳ ۱ ۰ مرتب‌سازی ادغامی
۵۰ ۴۶ ۴۲ ۳۸ ۳۴ ۳۰ ۲۶ ۲۲ ۱۹ ۱۶ ۱۳ ۱۰ ۷ ۵ ۳ ۱ ۰ مرتب‌سازی ادغام-درج

الگوریتم‌های بهینه تر

ویرایش

تا به امروز الگوریتم بهینه‌تر از نظر زمانی برای الگوریتم فورد-جانسون ارائه شده‌است که تعداد مقایسه‌های دقیقاً برابر فورد-جانسون است؛ امَا زمان کمتری می‌گیرد بدین گونه که به جای فراخوانی بازگشتی بر روی نصف لیست اعداد، بر روی یک چهارم لیست اعداد می‌باشد.[۵]

تا بیست سال الگوریتم فورد-جانسون، کمترین تعداد مقایسه را میان الگوریتم‌های مرتب‌سازی داشت. در سال ۱۹۷۹ گلن ماناکر الگوریتم مرتب‌سازی دیگری ارائه کرد که تعداد مقایسه‌های آن از فورد-جانسون حتی برای ورودی‌ها با تعداد زیاد نیز کمتر بود.

ماناکر نشان داد الگوریتم فورد-جانسون برای محدوده‌ای از مقادیر بهینه است. امروزه الگوریتمی ارائه شده‌است که به نتایج قوی‌تری نسبت به الگوریتم ماناکر دست یافته‌است.[۶]

منابع

ویرایش
  1. ۱٫۰ ۱٫۱ ۱٫۲ Knuth, Donald (1997), "§5.2.3, Sorting by Selection", Sorting and Searching, The Art of Computer Programming, 3 (third ed.), Addison-Wesley, pp. 144–155, ISBN 978-0-201-89685-5
  2. قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها، چاپ دوم، انتشارات فاطمی، ۱۳۸۹.
  3. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
  4. "هنر برنامه‌نویسی رایانه". ویکی‌پدیا، دانشنامهٔ آزاد. 2019-04-12.
  5. «ScienceDirect». www.sciencedirect.com. دریافت‌شده در ۲۰۱۹-۰۴-۱۶.
  6. «نتایج قوی‌تر از الگوریتم ماناکر».