الگوریتم مرتبسازی فورد-جانسون
الگو:ادغام به الگو:حق تکثیر مشکوک الگو:بهبود منبع الگو:جعبه اطلاعات الگوریتم الگوریتمهای متفاوتی برای مرتبسازی یک آرایه وجود دارد نظیر مرتبسازی حبابی، دودویی، انتخابی و ... و این الگوریتمها را از منظرهای متفاوتی نظیر میزان استفاده از فضای حافظه و ... میتوان مقایسه کرد که یکی از این مناظر تعداد مقایسهای است که در طول الگوریتم صورت میپذیرد، میدانیم که کمینه تعداد مقایسه لازم برای مرتبسازی 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، توابع بازگشتی بر روی لیستی به اندازهالگو:عبارت چپچین و سپس به روی آرایهای با طول الگو:عبارت چپچین و ... صورت میگیرد. برای این کار قسمت اول حافظه دیگیر میشود و قسمت دوم برای نگهداری اشارهگری به مکان اعضا نگه میدارد؛ بنابراین برای این الگوریتم ما از الگو:عبارت چپچین فضای حافظه استفاده میکند این در حالی است که الگوریتم اصلی فورد-جانسون از الگو:عبارت چپچین فضای حافظه استفاده میکند:الگو:سخ برای الگوریتم فورد-جانسون چهار الگو:عبارت چپچین الگو:سخ الگو:عبارت چپچین الگو:سخ برای الگوریتم اصلی فورد-جانسون الگو:عبارت چپچین الگو:سخ الگو:عبارت چپچین
- پس برای الگوریتم ما تنها ۳۳٪ فضای حافظه نسبت به الگوریتم اصلی فورد-جانسون مورد نیاز است.
- همچنین تعداد صدا زدن توابع بازگشتی الگوریتم پیشنهادی نسبت به فورد-جانسون اصلی براب با الگو:عبارت چپچین
جستارهای وابسته
منابع
- قدسی، محمد، داده ساختارها و مبانی الگوریتمها، چاپ دوم، انتشارات فاطمی، ۱۳۸۹.
- مقالهای از مارتین پکزارسکی در سال ۲۰۰۶
- مقالهای از مارسیو آیالا ریکون و برونو دآبرو در سال ۲۰۰۷