الگوریتم مرتب‌سازی فورد-جانسون

الگوریتم مرتب‌سازی فورد-جانسون

نمایش گرافیکی شیوه کار الگوریتم فورد-جانسون
رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه

الگوریتم‌های متفاوتی برای مرتب‌سازی یک آرایه وجود دارد نظیر مرتب‌سازی حبابی، دودویی، انتخابی و ... و این الگوریتم‌ها را از منظرهای متفاوتی نظیر میزان استفاده از فضای حافظه و ... می‌توان مقایسه کرد که یکی از این مناظر تعداد مقایسه‌ای است که در طول الگوریتم صورت می‌پذیرد، می‌دانیم که کمینه تعداد مقایسه لازم برای مرتب‌سازی n عنصر برابر با $\lceil log_{2}(n!)\rceil$ است و سؤالی که مطرح می‌شود این است که آیا الگوریتمی وجود دارد که با همین تعداد مقایسه، مرتب‌سازی را انجام دهد؟

جواب مثبت است. نام الگوریتمی که این کار را با این شرایط انجام می‌دهد الگوریتم فورد_جانسون یا الگوریتم الحاق ادغامی می‌باشد که روش کار آن، تعمیم آن، محاسبات و تخلیل آن در این مقاله بحث خواهد شد.
در سال ۱۹۵۹ آقایان لستر فورد و سلمر جانسون الگوریتمی که روش کار آن در قسمت پایین بحث شده‌است را تعمیم دادند که این تعمیم به احترام آنان الگوریتم مرتب‌سازی فورد_جانسون نام گرفت. ایده اصلی این الگوریتم تشکیل یک "زنجیره اصلی" از عناصری است که مرتب هستند و تعیین یک ترتیب مشخص برای درج دیگر عناصر در این زنجیره به طوری که در انتها، زنجیره اصلی شامل همه عناصر شود.

توضیح روش کار الگوریتم

روش کار این الگوریتم مطابق زیر است:(فرض می‌کنیم آرایه ما دارای عناصر {A1, A2, A3, A4, A5} است.

1. ابتدا A1 را با A2 و A3 را با A4 مقایسه کرده و عناصر کوچکتر و بزرگتر هر مقایسه را پیدا می‌کند. فرض را بر آن می‌گیریم که نتیجه مقایسه به این شکل است: $A1\leq A2,A3\leq A4$
2. با مقایسه دیگر، دو عنصر بزرگ- یعنی A2 , A4- را با هم مقایسه می‌کند- فرض کنیم $A2\leq A4$
3. ابتدا A5 را در عبارت $A1\leq A2\leq A4$ به روش دودویی درج می‌کند که این کار حداکثر دو مقایسه نیاز دارد
4. با توجه به این که $A3\leq A4$، درج A3 در سه‌تایی A1, A2, A5 یا دوتایی $A1\leq A2$، به روش دودویی حداکثر دو مقایسهٔ دیگر نیاز دارد.
   

بنابراین برای تعداد عناصر زیر تعداد مقایسه‌ها به شکل زیر است:

مقدار n	تعداد مقایسه
۱	۰
۲	۱
۳	۳
...	...
n	$\lceil nlog(n)\rceil$

الگوریتم تعمیم یافته توسط آقایان فورد و جانسون

این الگوریتم برای یک مجموعه n عضوی به شکل زیر عمل می‌کند:

1. n عضو را اگر n زوج باشد به ${\frac {n}{2}}$ مجموعه دو عضوی و اگر فرد باشد به $\lfloor {\frac {n}{2}}\rfloor$ مجموعه دو عضوی و یک مجموعه یک عضوی تقسیم می‌کنیم.
2. هر کدام از این مجموعه‌ها را مقایسه و مرتب می‌کنیم.
3. اعضای بزرگتر این مجموعه‌ها را با یکدیگر مقایسه کرده و به نامساوی به شکل $A1\leq A2\leq A3\leq ...\leq A_{\lfloor {\frac {n}{2}}\rfloor }$ می‌شود که $A_{i}$ها اعضای بزرگ مجموعه‌هاست. این زنجیره متشکل از $A_{i}$ها "زنجیره اصلی" نام دارد.
4. حال باید عناصر باقی‌مانده که وارد زنجیره اصلی نشده‌است را به روش مرتب‌سازی دودویی وارد آن کنیم. برای این کار به روش زیر عمل می‌کنیم-این اعضا را با $B_{i}$ها نمایش می‌دهیم-:

• ابتدا $B_{3}$ را به $B1\leq A1\leq A2$ و سپس $B_{2}$ را به $B1\leq A1$ و $B_{3}$ اضافه می‌کند که از آنجا که هر زنجیره سه عضو دارد دو مقایسه کافیست.
• ابتدا $B_{5}$ را به زنجیره شامل ۷ عنصر $A_{1}$ تا $A_{4}$ و $B_{1}$ تا $B_{3}$ درج می‌کند. سپس $B_{4}$ درج می‌کند. تعداد عناصر این زنجیره حداکثر ۷ و هر درج با ۳ مقایسه امکان‌پذیر است.
• این روند را ادامه می‌دهد. در حالت کلی اگر $T_{1},T_{2},...=1,3,5,11,...$، در مرحلهٔ 1<kام هر عنصر $B_{T_{k}}$ تا $B_{T_{k-1}+1}$ را به همین ترتیب در زنجیرهٔ عناصر که حتماً کوچک‌تر یا مساوی با آن عنصر هستند، درج می‌کند که یعنی نهایتاً در آخرین مرحله دارای $B_{\lfloor {\frac {n}{2}}\rfloor +1}$ هستیم.

دسته‌بندی در الگوریتم فورد-جانسون.

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

در این‌جا می‌خواهیم بررسی کنیم که الگوریتم فورد-جانسون تا کجا پایایی خورد را حفظ می‌کند، به این معنا که تا کجا این الگوریتم دارای کمترین تعداد مقایسه بین الگوریتم‌های مرتب‌سازی است. در ابتدا با یک مثال شروع می‌کنیم:
فرض کنیم $S(n)$ تعداد حداقل مقایسه‌ها برای مرتب‌سازی آرایه‌ای به طول n باشد و $F(n)$ تعداد مقایسه‌هایی است که الگوریتم فورد-جانسون انجام می‌دهد. محاسبات رایانه‌ای نشان می‌دهد که برای هر n طبیعی تا $F(22)=S(22)=71,n=22$. همچنین بدست می‌آید که الگوریتم فورد جانسون برای $n\leq 15,n=20,21,22$ بهینه می‌باشد. اما انجام کمترین مقایسه برای همه nها متعلق به الگوریتم فورد-جانسون نیست بلکه بدست آمده است که n=۴۷ کوچکترین عددی است که الگوریتمی بهینه‌تر از فورد-جانسون برای مرتب‌سازی آن پیدا می‌شود، برای این مقدار n این الگوریتم که توسط Schulte Monting بدست آمده است با ۲۰۰ مقایسه آرایه را مرتب می‌کند در حالی که الگوریتم فورد-جانسود آن را با ۲۰۱ مقایسه مرتب می‌سازد؛ بنابراین پایداری الگوریتم فورد جانسون به عنوان بهینه‌ترین الگوریتم از نظر مقایسه تا $n\leq 46$ ادامه دارد و پس از آن این الگوریتم بهینگی خود را نسبت به سایر الگوریتم‌ها از دست می‌دهد؛ بنابراین برای nهای کوچک الگوریتم فورد جانسون بهترین است اما از یک جایی به بعد این الگوریتم شکست می‌خورد.

الگوریتمی متفاوت از فورد-جانسون

همان‌طور که قبلاً ذکر شد، یک دیگر از ملاک‌های بهینه بودن یک الگوریتم، بهینه بودن از نظر میزان استفاده از فضای حافظه است و به‌دلیل وجود توابع بازگشتی بسیار در الگوریتم فورد-جانسون، این الگوریتم از منظر فضای مورد استفاده، بهینه تلقی نمی‌شود. در این بخش ما به معرفی حالتی مختلف از الگوریتم فورد جانسون می‌پردازیم که از نظر استفاده از حافظه از الگوریتم مطرح شده در بخش قبل بهینه‌تر است.
پدیدآورندگان این الگوریتم آن را فورد-جانسون چهار نام‌گذاری کرده‌اند. فرق این الگوریتم با الگوریتم اصلی فورد-جانسون در آن است که بجای این که به‌طور بازگشتی روی آرایه‌ای به طول نصف آرایه ورودی کار کند، روی آرایه‌ای به طول ربع آرایه ورودی کار می‌کند و این می‌تواند تعداد صدا زدن‌های بازگشتی توابع را تا ۳۳٪ کاهش دهد.
در الگوریتم فورد-جانسون چهار، توابع بازگشتی، لیست ورودی را به چهار بخش تقسیم می‌کند که هر کدام از این ربع‌ها با سه مقایسه به دست می‌آید که نام هرکدام از این بخش‌ها را با توجه به اعضا یک از نام‌های ماکزیموم (max)، انتظار (pend)، کمتر از انتظار (ltp) و کمتر از ماکسیموم (ltm) می‌گذاریم که این ۴تا را به صورت چهار ضلع یک چهارضلعی نمایش می‌دهیم.

الگوریتمی با مصرف فضای حافظه کمتر.

این الگوریتم شامل چهار مرحله زیر است:

1. ابتدا لیست ورودی را به $\lfloor {\frac {n}{4}}\rfloor$ بخش کوچکتر چهار عضوی تقسیم می‌کنیم که در هر بخش چهارعضوی اعضا را در اضلاع چهار ضلعی قرار می‌دهیم یعنی پس از آن مجموعه‌ای از چهارضلعی‌ها را خواهیم داشت. حال اگر باقی‌مانده n به ۴ مساوی ۲ باشد، بین دو عضو باقی‌مانده، عضو بزرگتر را با pend و آن یکی را ltp می‌گیریم و اگر باقی‌مانده ۳ باشد، سومی را ltm در نظر می‌گیریم و اگر باقی‌مانده ۱ باشد، تک عضو باقی‌مانده را ltm در نظر می‌گیریم.
2. در هر بخش (هر چهارضلعی) اعضا را با مقایسه مرتب می‌کنیم.
3. از آنجا که در مرحله قبل maxها را در هر چهار ضلعی بدست آورده‌ایم، مانند الگوریتم اصلی فورد-جانسون زنجیره اصلی را تشکیل می‌دهیم؛ و سپس اعضای pend را با استفاده از الحاق دودویی در آن وارد می‌کینم.
4. حال ما ساختاری شامل زنجیره اصلی به اندازه $\lfloor {\frac {n}{2}}\rfloor$ داریم که لیست مرتب‌شده‌ای از همه اعداد pend، max و ltmو ltpهای متناظر است. سپس در قدم نهایی، عناصر ltm و ltp را با استفاده از الحاق دودویی مانند الگوریتم اصلی وارد زنجیره اصلی می‌کنیم.
   

این مراحل در اشکال زیر به ترتیب نمایش داده می‌شود:

مرحله یک.

مرحله دو.

مرحله سه.

• این عناصر وابسته در سومین شکل نشان از ltp و ltmهای وابسته به pend و maxها دارد که در مرحله چهارم وارد کل زنجیره می‌شود.

اثبات

در این قسمت می‌خواهیم اثبات کنیم که الگوریتم پیشنهادی قبل دقیقاً به تعداد الگوریتم فورد-جانسون معمولی مقایسه انجام می‌دهد، درحالی که میزان حافظه استفاده شده در آن کمتر است.
در الگوریتم فورد-جانسون چهار توابع بازگشتی به طوری محلی صدا زده می‌شوند، به این معنا که چهارضلعی‌ها در هر مرحله از توابع محلی بدست می‌آیند و تابع بازگشتی روی آرایه‌ای با اندازه ربع آرایه ورودی اتفاق می‌افتد، یعنی در این الگوریتم برای آرایه‌ای با طول n، توابع بازگشتی بر روی لیستی به اندازه$\lfloor {\frac {n}{4}}\rfloor$ و سپس به روی آرایه‌ای با طول $\lfloor {\frac {n}{4^{2}}}\rfloor$ و ... صورت می‌گیرد. برای این کار قسمت اول حافظه دیگیر می‌شود و قسمت دوم برای نگه‌داری اشاره‌گری به مکان اعضا نگه می‌دارد؛ بنابراین برای این الگوریتم ما از $\sum _{i=1}^{\lceil log_{4}(n)\rceil -1}\lfloor {\frac {n}{4^{i}}}\rfloor$ فضای حافظه استفاده می‌کند این در حالی است که الگوریتم اصلی فورد-جانسون از $\sum _{i=1}^{\lceil log_{2}(n)\rceil -1}\lfloor {\frac {n}{2^{i}}}\rfloor$ فضای حافظه استفاده می‌کند:
برای الگوریتم فورد-جانسون چهار $\leftarrow$
$\sum _{i=1}^{\lceil log_{4}(n)\rceil -1}\lfloor {\frac {n}{4^{i}}}\rfloor =\sum _{j=1}^{k-1}4^{j}{\frac {1}{3}}(4^{k}-1)-1={\frac {1}{3}}n-{\frac {4}{3}}$
برای الگوریتم اصلی فورد-جانسون $\leftarrow$
$\sum _{i=1}^{\lceil log_{2}(n)\rceil -1}\lfloor {\frac {n}{2^{i}}}\rfloor =\sum _{j=1}^{2k-1}2^{j}=2^{2k}-1-1=n-2$

• پس برای الگوریتم ما تنها ۳۳٪ فضای حافظه نسبت به الگوریتم اصلی فورد-جانسون مورد نیاز است.
• همچنین تعداد صدا زدن توابع بازگشتی الگوریتم پیشنهادی نسبت به فورد-جانسون اصلی براب با ${\frac {\lfloor log_{4}(n)\rfloor }{\lfloor log_{2}(n)\rfloor }}\leq {\frac {1}{2}}$

جستارهای وابسته

• مرتب‌سازی حبابی
• مرتب‌سازی انتخابی
• مرتب‌سازی هرمی
• مرتب‌سازی ادغامی

منابع

• قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها، چاپ دوم، انتشارات فاطمی، ۱۳۸۹.
• مقاله‌ای از مارتین پکزارسکی در سال ۲۰۰۶
• مقاله‌ای از مارسیو آیالا ریکون و برونو دآبرو در سال ۲۰۰۷