موضوع مقاله: الگوریتم مرتب‌سازی فورد-جانسون | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم مرتب‌سازی فورد-جانسون | مقدمه: الگوریتم‌های متفاوتی برای مرتب‌سازی یک آرایه وجود دارد نظیر مرتب‌سازی حبابی، دودویی، انتخابی و ... | ## بخش 1: الگوریتم مرتب‌سازی فورد-جانسون | می‌توان مقایسه کرد که یکی از این مناظر تعداد مقایسه‌ای است که در طول الگوریتم صورت می‌پذیرد، می‌دانیم که کمینه تعداد مقایسه لازم برای مرتب‌سازی n عنصر برابر با است و سؤالی که مطرح می‌شود این است که آیا الگوریتمی وجود دارد که با همین تعداد مقایسه، مرتب‌سازی را انجام دهد؟ نام الگوریتمی که این کار را با این شرایط انجام می‌دهد الگوریتم فورد_جانسون یا الگوریتم الحاق ادغامی می‌باشد که روش کار آن، تعمیم آن، محاسبات و تخلیل آن در این مقاله بحث خواهد شد. در سال ۱۹۵۹ آقایان لستر فورد و سلمر جانسون الگوریتمی که روش کار آن در قسمت پایین بحث شده‌است را تعمیم دادند که این تعمیم به احترام آنان الگوریتم مرتب‌سازی فورد_جانسون نام گرفت. ایده اصلی این الگوریتم تشکیل یک "زنجیره اصلی" از عناصری است که مرتب هستند و تعیین یک ترتیب مشخص برای درج دیگر عناصر در این زنجیره به طوری که در انتها، زنجیره اصلی شامل همه عناصر شود. توضیح روش کار الگوریتم روش کار این الگوریتم مطابق زیر است:(فرض می‌کنیم آرایه ما دارای عناصر } است. ابتدا A1 را با A2 و A3 را با A4 مقایسه کرده و عناصر کوچکتر و بزرگتر هر مقایسه را پیدا می‌کند. فرض را بر آن می‌گیریم که نتیجه مقایسه به این شکل است: با مقایسه دیگر، دو عنصر بزرگ- یعنی A2 , A4- را با هم مقایسه می‌کند- فرض کنیم ابتدا A5 را در عبارت به روش دودویی درج می‌کند که این کار حداکثر دو مقایسه نیاز دارد با توجه به این که ، درج A3 در سه‌تایی A1, A2, A5 یا دوتایی ، به روش دودویی حداکثر دو مقایسهٔ دیگر نیاز دارد. بنابراین برای تعداد عناصر زیر تعداد مقایسه‌ها به شکل زیر است: مقدار n تعداد مقایسه ۱ ۰ ۲ ۱ ۳ ۳ ... n الگوریتم تعمیم یافته توسط آقایان فورد و جانسون این الگوریتم برای یک مجموعه n عضوی به شکل زیر عمل می‌کند: n عضو را اگر n زوج باشد به مجموعه دو عضوی و اگر فرد باشد به مجموعه دو عضوی و یک مجموعه یک عضوی تقسیم می‌کنیم. | ## بخش 2: الگوریتم مرتب‌سازی فورد-جانسون | اعضای بزرگتر این مجموعه‌ها را با یکدیگر مقایسه کرده و به نامساوی به شکل می‌شود که ها اعضای بزرگ مجموعه‌هاست. حال باید عناصر باقی‌مانده که وارد زنجیره اصلی نشده‌است را به روش مرتب‌سازی دودویی وارد آن کنیم. برای این کار به روش زیر عمل می‌کنیم-این اعضا را با ها نمایش می‌دهیم-: ابتدا را به و سپس را به و اضافه می‌کند که از آنجا که هر زنجیره سه عضو دارد دو مقایسه کافیست. در حالت کلی اگر ، در مرحلهٔ 1<kام هر عنصر تا را به همین ترتیب در زنجیرهٔ عناصر که حتماً کوچک‌تر یا مساوی با آن عنصر هستند، درج می‌کند که یعنی نهایتاً در آخرین مرحله دارای هستیم. پایایی الگوریتم در این‌جا می‌خواهیم بررسی کنیم که الگوریتم فورد-جانسون تا کجا پایایی خورد را حفظ می‌کند، به این معنا که تا کجا این الگوریتم دارای کمترین تعداد مقایسه بین الگوریتم‌های مرتب‌سازی است. در ابتدا با یک مثال شروع می‌کنیم: فرض کنیم تعداد حداقل مقایسه‌ها برای مرتب‌سازی آرایه‌ای به طول n باشد و تعداد مقایسه‌هایی است که الگوریتم فورد-جانسون انجام می‌دهد. اما انجام کمترین مقایسه برای همه nها متعلق به الگوریتم فورد-جانسون نیست بلکه به‌دست آمده است که n=۴۷ کوچکترین عددی است که الگوریتمی بهینه‌تر از فورد-جانسون برای مرتب‌سازی آن پیدا می‌شود، برای این مقدار n این الگوریتم که توسط Schulte Monting به‌دست آمده است با ۲۰۰ مقایسه آرایه را مرتب می‌کند در حالی که الگوریتم فورد-جانسود آن را با ۲۰۱ مقایسه مرتب می‌سازد؛ بنابراین پایداری الگوریتم فورد جانسون به عنوان بهینه‌ترین الگوریتم از نظر مقایسه تا ادامه دارد و پس از آن این الگوریتم بهینگی خود را نسبت به سایر الگوریتم‌ها از دست می‌دهد؛ بنابراین برای nهای کوچک الگوریتم فورد جانسون بهترین است اما از یک جایی به بعد این الگوریتم شکست می‌خورد. الگوریتمی متفاوت از فورد-جانسون همان‌طور که قبلاً ذکر شد، یک دیگر از ملاک‌های بهینه بودن یک الگوریتم، بهینه بودن از نظر میزان استفاده از فضای حافظه است و به‌دلیل وجود توابع بازگشتی بسیار در الگوریتم فورد-جانسون، این الگوریتم از منظر فضای مورد استفاده، بهینه تلقی نمی‌شود. در این بخش ما به معرفی حالتی مختلف از الگوریتم فورد جانسون می‌پردازیم که از نظر استفاده از حافظه از الگوریتم مطرح شده در بخش قبل بهینه‌تر است. | ## بخش 3: الگوریتم مرتب‌سازی فورد-جانسون | فرق این الگوریتم با الگوریتم اصلی فورد-جانسون در آن است که به‌جای این که به‌طور بازگشتی روی آرایه‌ای به طول نصف آرایه ورودی کار کند، روی آرایه‌ای به طول ربع آرایه ورودی کار می‌کند و این می‌تواند تعداد صدا زدن‌های بازگشتی توابع را تا ۳۳٪ کاهش دهد. در الگوریتم فورد-جانسون چهار، توابع بازگشتی، لیست ورودی را به چهار بخش تقسیم می‌کند که هر کدام از این ربع‌ها با سه مقایسه به دست می‌آید که نام هرکدام از این بخش‌ها را با توجه به اعضا یک از نام‌های ماکزیموم (max)، انتظار (pend)، کمتر از انتظار (ltp) و کمتر از ماکسیموم (ltm) می‌گذاریم که این ۴تا را به صورت چهار ضلع یک چهارضلعی نمایش می‌دهیم. این الگوریتم شامل چهار مرحله زیر است: ابتدا لیست ورودی را به بخش کوچکتر چهار عضوی تقسیم می‌کنیم که در هر بخش چهارعضوی اعضا را در اضلاع چهار ضلعی قرار می‌دهیم یعنی پس از آن مجموعه‌ای از چهارضلعی‌ها را خواهیم داشت. حال اگر باقی‌مانده n به ۴ مساوی ۲ باشد، بین دو عضو باقی‌مانده، عضو بزرگتر را با pend و آن یکی را ltp می‌گیریم و اگر باقی‌مانده ۳ باشد، سومی را ltm در نظر می‌گیریم و اگر باقی‌مانده ۱ باشد، تک عضو باقی‌مانده را ltm در نظر می‌گیریم. از آنجا که در مرحله قبل maxها را در هر چهار ضلعی به‌دست آورده‌ایم، مانند الگوریتم اصلی فورد-جانسون زنجیره اصلی را تشکیل می‌دهیم؛ و سپس اعضای pend را با استفاده از الحاق دودویی در آن وارد می‌کینم. سپس در قدم نهایی، عناصر ltm و ltp را با استفاده از الحاق دودویی مانند الگوریتم اصلی وارد زنجیره اصلی می‌کنیم. اثبات در این قسمت می‌خواهیم اثبات کنیم که الگوریتم پیشنهادی قبل دقیقاً به تعداد الگوریتم فورد-جانسون معمولی مقایسه انجام می‌دهد، درحالی که میزان حافظه استفاده شده در آن کمتر است. در الگوریتم فورد-جانسون چهار توابع بازگشتی به طوری محلی صدا زده می‌شوند، به این معنا که چهارضلعی‌ها در هر مرحله از توابع محلی به‌دست می‌آیند و تابع بازگشتی روی آرایه‌ای با اندازه ربع آرایه ورودی اتفاق می‌افتد، یعنی در این الگوریتم برای آرایه‌ای با طول n، توابع بازگشتی بر روی لیستی به اندازه و سپس به روی آرایه‌ای با طول و ... | ## جمع‌بندی | برای این کار قسمت اول حافظه دیگیر می‌شود و قسمت دوم برای نگه‌داری اشاره‌گری به مکان اعضا نگه می‌دارد؛ بنابراین برای این الگوریتم ما از فضای حافظه استفاده می‌کند این در حالی است که الگوریتم اصلی فورد-جانسون از فضای حافظه استفاده می‌کند: برای الگوریتم فورد-جانسون چهار برای الگوریتم اصلی فورد-جانسون پس برای الگوریتم ما تنها ۳۳٪ فضای حافظه نسبت به الگوریتم اصلی فورد-جانسون مورد نیاز است.