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

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

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

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

فرض می‌کنیم ۵ عدد داریم ($a,b,c,d,e$)، آن‌ها را به سه دسته تقسیم می‌کنیم: $(a,b)(c,d)(e)$

سپس دو عدد موجود در دسته‌های دوتایی را باهم مقایسه می‌کنیم و بعد از آن دو عدد بزرگتر هر دسته را با یکدیگر مقایسه می‌کنیم. فرض می‌کنیم $a>b,c>d$. آنگاه باید دو عدد $a,c$ را با هم مقایسه کنیم. در شکل‌های زیر جهت پیکان از عدد کوچکتر به سمت عدد بزرگتر است.

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

الگوریتم

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

ادغام

1. $n$ عنصر موجود را به $\left\lfloor {\frac {n}{2}}\right\rfloor$ گروه دوتایی تقسیم می‌کنیم؛ و اگر $n$ فرد بود، یک عنصر جفت نشده باقی می‌ماند.
2. $\left\lfloor {\frac {n}{2}}\right\rfloor$مقایسه انجام می‌دهیم تا عنصر بزرگتر در هر گروه را بیابیم.
3. $\left\lfloor {\frac {n}{2}}\right\rfloor$ عنصر بزرگتر را به شکل بازگشتی مرتب می‌کنیم. حال عناصر مرتب شده را زنجیره اصلی می‌نامیم که به صورت $a_{i}$در شکل نمایش داده شده‌است.

   

4. سپس با توجه به این که زنجیره اصلی مرتب شده‌است و عنصر $a_{1}$ کوچکترین عنصر زنجیره است و می‌دانیم $b_{1}$ از آن کوچکتر است، بنابراین می‌توان $b_{1}$ را در ابتدای زنجیره درج نمود.
5. بقیه عناصر که به شکل $b_{i}$ نشان داده شده‌است را در زنجیره اصلی درج می‌کنیم. (با استفاده از مرتب‌سازی درجی)

درج

روش درج کردن $b_{i}$ها به ترتیب زیر است:

$b_{3},b_{2};b_{5},b_{4};b_{1}1,b_{1}0,...,b_{6};.....;b_{t_{k}},b_{t_{k-1}},......,b_{t_{k-1}}+1$

$(t_{1},t_{2},t_{3},t_{4},...)=(1,3,5,11,...)$

سپس در آخر در صورت وجود، $b_{{\left\lfloor {\frac {n}{2}}\right\rfloor }+1}$ را در زنجیره اصلی درج می‌نماییم.

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

برای بررسی تعداد مقایسه‌ها ابتدا به مقادیر $t_{k}$ها می‌پردازیم. این مقادیر باید باید به گونه‌ای باشند که تعداد عناصر زنجیره اصلی هنگام درج یک عنصر در مرحله $k$ام برابر $2^{k}-1$باشد.

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

$2t_{k-1}+(t_{k}-t_{k-1})-1=2^{k}-1\Longrightarrow t_{k}+t_{k-1}=2^{k},t_{1}=1$

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

$t_{k}={\frac {1}{3}}(2^{k+1}+(-1)^{k})$

$F(n)$را تعداد مقایسه‌های الگوریتم فورد-جانسون برای $n$عنصر می‌گیریم. ابتدا $\left\lfloor {\frac {n}{2}}\right\rfloor$مقایسه برای پیدا کردن عنصر بزرگتر در هر دسته داریم و سپس زنجیره اصلی را به شکل بازگشتی مرتب می‌کنیم و $G$هم تعداد مقایسه‌ها برای درج عناصر کوچکتر دسته‌ها در زنجیره اصلی است.

$F(n)=\left\lfloor {\frac {n}{2}}\right\rfloor +F({\left\lfloor {\frac {n}{2}}\right\rfloor })+G({\left\lceil {\frac {n}{2}}\right\rceil })$

و برای هر $t_{k-1}\leq n\leq t_{k}$،$G(n)$برابر است با $\sum _{j=1}^{k-1}[j(t_{j}-t_{j-1})]+k(n-t_{k-1})$.

$\sum _{j=1}^{k-1}[j(t_{j}-t_{j-1})]+k(n-t_{k-1})=kn-(t_{0}+t_{1}+t_{2}+...+t_{k-1})$

$w_{k}=t_{0}+t_{1}+t_{2}+...+t_{k-1}\Longrightarrow (w_{0},w_{1},w_{2},w_{3},...)=(0,1,2,5,...)$

پس از تعریف $w_{k}$به شکل بالا می‌توان ثابت کرد : $F(n)-F(n-1)=k\Longleftrightarrow w_{k}<n\leq w_{k+1}$

و شرط بالا معادل است با : ${\frac {2^{k+1}}{3}}<n<{\frac {2^{k+2}}{3}}\Longrightarrow k+1<log(3n)\leq k+2$

بنابرابن داریم : $F(n)-F(n-1)=\left\lceil log({\frac {3}{4}}n)\right\rceil$

در نتیجه: $F(n)=\sum _{k=1}^{n}\left\lceil log({\frac {3}{4}}k)\right\rceil$

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

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

تعداد مقایسه‌های این الگوریتم مرتب‌سازی برای $n\leq 11$برابر با کران پایین تعداد مقایسه‌های مرتب‌سازی‌های مقایسه‌ای است. این کران پایین برابر است با $\lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n$

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

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

تعداد مقایسه‌ها در بدترین حالت

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

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

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

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

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