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