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

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