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

{{ادغام به|مرتب‌سازی ادغام-درج|تاریخ=مارس ۲۰۲۰}}
{{حق تکثیر مشکوک|تاریخ=مارس ۲۰۱۶}}
{{بهبود منبع|تاریخ=مارس ۲۰۱۶}}
{{جعبه اطلاعات الگوریتم
| کلاس           = [[الگوریتم مرتب‌سازی]]
| تصویر         = [[پرونده:Ford-janson.gif|بندانگشتی|نمایش گرافیکی شیوه کار الگوریتم فورد-جانسون]]
| داده‌ها        = [[آرایه (ساختار داده)|آرایه]]
}}
الگوریتم‌های متفاوتی برای مرتب‌سازی یک آرایه وجود دارد نظیر مرتب‌سازی حبابی، دودویی، انتخابی و ... و این الگوریتم‌ها را از منظرهای متفاوتی نظیر میزان استفاده از فضای حافظه و ... می‌توان مقایسه کرد که یکی از این مناظر تعداد مقایسه‌ای است که در طول الگوریتم صورت می‌پذیرد، می‌دانیم که کمینه تعداد مقایسه لازم برای مرتب‌سازی n عنصر برابر با {{عبارت چپ‌چین|<math>\lceil log_2(n!) \rceil</math>}} است و سؤالی که مطرح می‌شود این است که آیا الگوریتمی وجود دارد که با همین تعداد مقایسه، مرتب‌سازی را انجام دهد؟

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

== توضیح روش کار الگوریتم ==
روش کار این الگوریتم مطابق زیر است:(فرض می‌کنیم آرایه ما دارای عناصر {{عبارت چپ‌چین|{A1, A2, A3, A4, A5}}} است.
# ابتدا A1 را با A2 و A3 را با A4 مقایسه کرده و عناصر کوچکتر و بزرگتر هر مقایسه را پیدا می‌کند. فرض را بر آن می‌گیریم که نتیجه مقایسه به این شکل است: {{عبارت چپ‌چین|<math>A1\leq A2 , A3\leq A4</math>}}
# با مقایسه دیگر، دو عنصر بزرگ- یعنی A2 , A4- را با هم مقایسه می‌کند- فرض کنیم {{عبارت چپ‌چین|<math>A2\leq A4</math>}}
# ابتدا A5 را در عبارت {{عبارت چپ‌چین|<math>A1\leq A2\leq A4</math>}} به روش دودویی درج می‌کند که این کار حداکثر دو مقایسه نیاز دارد
# با توجه به این که {{عبارت چپ‌چین|<math>A3\leq A4</math>}}، درج A3 در سه‌تایی A1, A2, A5 یا دوتایی {{عبارت چپ‌چین|<math>A1\leq A2</math>}}، به روش دودویی حداکثر دو مقایسهٔ دیگر نیاز دارد.{{سخ}}
بنابراین برای تعداد عناصر زیر تعداد مقایسه‌ها به شکل زیر است:{{سخ}}
{| class="wikitable"
|-
! مقدار n !! تعداد مقایسه
|-
| ۱ || ۰
|-
| ۲ || ۱
|-
| ۳ || ۳
|-
| ... || ...
|-
| n || {{عبارت چپ‌چین|<math>\lceil nlog(n) \rceil</math>}}
|}

== الگوریتم تعمیم یافته توسط آقایان فورد و جانسون ==
این الگوریتم برای یک مجموعه n عضوی به شکل زیر عمل می‌کند:
# n عضو را اگر n زوج باشد به {{عبارت چپ‌چین|<math>\frac{n}{2}</math>}} مجموعه دو عضوی و اگر فرد باشد به {{عبارت چپ‌چین|<math>\lfloor \frac{n}{2} \rfloor</math>}} مجموعه دو عضوی و یک مجموعه یک عضوی تقسیم می‌کنیم.
# هر کدام از این مجموعه‌ها را مقایسه و مرتب می‌کنیم.
# اعضای بزرگتر این مجموعه‌ها را با یکدیگر مقایسه کرده و به نامساوی به شکل {{عبارت چپ‌چین|<math>A1\leq A2 \leq A3 \leq ... \leq A_{\lfloor \frac{n}{2} \rfloor}</math>}} می‌شود که {{عبارت چپ‌چین|<math>A_i</math>}}ها اعضای بزرگ مجموعه‌هاست. این زنجیره متشکل از {{عبارت چپ‌چین|<math>A_i</math>}}ها "زنجیره اصلی" نام دارد.
# حال باید عناصر باقی‌مانده که وارد زنجیره اصلی نشده‌است را به روش مرتب‌سازی دودویی وارد آن کنیم. برای این کار به روش زیر عمل می‌کنیم-این اعضا را با {{عبارت چپ‌چین|<math>B_i</math>}}ها نمایش می‌دهیم-:
* ابتدا {{عبارت چپ‌چین|<math>B_3</math>}} را به {{عبارت چپ‌چین|<math>B1\leq A1 \leq A2</math>}} و سپس {{عبارت چپ‌چین|<math>B_2</math>}} را به {{عبارت چپ‌چین|<math>B1\leq A1</math>}} و {{عبارت چپ‌چین|<math>B_3</math>}} اضافه می‌کند که از آنجا که هر زنجیره سه عضو دارد دو مقایسه کافیست.
* ابتدا {{عبارت چپ‌چین|<math>B_5</math>}} را به زنجیره شامل ۷ عنصر {{عبارت چپ‌چین|<math>A_1</math>}} تا {{عبارت چپ‌چین|<math>A_4</math>}} و {{عبارت چپ‌چین|<math>B_1</math>}} تا {{عبارت چپ‌چین|<math>B_3</math>}} درج می‌کند. سپس {{عبارت چپ‌چین|<math>B_4</math>}} درج می‌کند. تعداد عناصر این زنجیره حداکثر ۷ و هر درج با ۳ مقایسه امکان‌پذیر است.
* این روند را ادامه می‌دهد. در حالت کلی اگر {{عبارت چپ‌چین|<math>T_1, T_2, ... = 1, 3, 5, 11, ...</math>}}، در مرحلهٔ 1<kام هر عنصر {{عبارت چپ‌چین|<math>B_{T_{k}}</math>}} تا {{عبارت چپ‌چین|<math>B_{T_{k-1}+1}</math>}} را به همین ترتیب در زنجیرهٔ عناصر که حتماً کوچک‌تر یا مساوی با آن عنصر هستند، درج می‌کند که یعنی نهایتاً در آخرین مرحله دارای {{عبارت چپ‌چین|<math>B_{\lfloor \frac{n}{2} \rfloor + 1}</math>}} هستیم.
[[پرونده:الگوریتم فورد-جانسون.png|وسط|362px|راست|دسته‌بندی در الگوریتم فورد-جانسون.]]

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

== الگوریتمی متفاوت از فورد-جانسون ==
همان‌طور که قبلاً ذکر شد، یک دیگر از ملاک‌های بهینه بودن یک الگوریتم، بهینه بودن از نظر میزان استفاده از فضای حافظه است و به‌دلیل وجود [[توابع بازگشتی]] بسیار در الگوریتم فورد-جانسون، این الگوریتم از منظر فضای مورد استفاده، بهینه تلقی نمی‌شود. در این بخش ما به معرفی حالتی مختلف از الگوریتم فورد جانسون می‌پردازیم که از نظر استفاده از حافظه از الگوریتم مطرح شده در بخش قبل بهینه‌تر است.{{سخ}}
پدیدآورندگان این الگوریتم آن را فورد-جانسون چهار نام‌گذاری کرده‌اند. فرق این الگوریتم با الگوریتم اصلی فورد-جانسون در آن است که بجای این که به‌طور بازگشتی روی آرایه‌ای به طول نصف آرایه ورودی کار کند، روی آرایه‌ای به طول ربع آرایه ورودی کار می‌کند و این می‌تواند تعداد صدا زدن‌های بازگشتی توابع را تا ۳۳٪ کاهش دهد.{{سخ}}
در الگوریتم فورد-جانسون چهار، توابع بازگشتی، لیست ورودی را به چهار بخش تقسیم می‌کند که هر کدام از این ربع‌ها با سه مقایسه به دست می‌آید که نام هرکدام از این بخش‌ها را با توجه به اعضا یک از نام‌های ماکزیموم (max)، انتظار (pend)، کمتر از انتظار (ltp) و کمتر از ماکسیموم (ltm) می‌گذاریم که این ۴تا را به صورت چهار ضلع یک چهارضلعی نمایش می‌دهیم.
[[پرونده:الگوریتم جدید.png|وسط|362px|راست|الگوریتمی با مصرف فضای حافظه کمتر.]]
این الگوریتم شامل چهار مرحله زیر است:
# ابتدا لیست ورودی را به {{عبارت چپ‌چین|<math> \lfloor \frac{n}{4} \rfloor</math>}} بخش کوچکتر چهار عضوی تقسیم می‌کنیم که در هر بخش چهارعضوی اعضا را در اضلاع چهار ضلعی قرار می‌دهیم یعنی پس از آن مجموعه‌ای از چهارضلعی‌ها را خواهیم داشت. حال اگر باقی‌مانده n به ۴ مساوی ۲ باشد، بین دو عضو باقی‌مانده، عضو بزرگتر را با pend و آن یکی را ltp می‌گیریم و اگر باقی‌مانده ۳ باشد، سومی را ltm در نظر می‌گیریم و اگر باقی‌مانده ۱ باشد، تک عضو باقی‌مانده را ltm در نظر می‌گیریم.
# در هر بخش (هر چهارضلعی) اعضا را با مقایسه مرتب می‌کنیم.
# از آنجا که در مرحله قبل maxها را در هر چهار ضلعی بدست آورده‌ایم، مانند الگوریتم اصلی فورد-جانسون '''زنجیره اصلی''' را تشکیل می‌دهیم؛ و سپس اعضای pend را با استفاده از الحاق دودویی در آن وارد می‌کینم.
# حال ما ساختاری شامل زنجیره اصلی به اندازه {{عبارت چپ‌چین|<math> \lfloor \frac{n}{2} \rfloor</math>}} داریم که لیست مرتب‌شده‌ای از همه اعداد pend، max و ltmو ltpهای متناظر است. سپس در قدم نهایی، عناصر ltm و ltp را با استفاده از الحاق دودویی مانند الگوریتم اصلی وارد زنجیره اصلی می‌کنیم.{{سخ}}
این مراحل در اشکال زیر به ترتیب نمایش داده می‌شود:
[[پرونده:مرحله یک الگوریتم جدید.png|وسط|362px|راست|مرحله یک.]]
[[پرونده:مرحله سه الگوریتم جدید.png|وسط|362px|راست|مرحله دو.]]
[[پرونده:مرحله الگوریتم جدید.png|وسط|362px|راست|مرحله سه.]]
* این عناصر وابسته در سومین شکل نشان از ltp و ltmهای وابسته به pend و maxها دارد که در مرحله چهارم وارد کل زنجیره می‌شود.

== اثبات ==
در این قسمت می‌خواهیم اثبات کنیم که الگوریتم پیشنهادی قبل دقیقاً به تعداد الگوریتم فورد-جانسون معمولی مقایسه انجام می‌دهد، درحالی که میزان حافظه استفاده شده در آن کمتر است.{{سخ}}
در الگوریتم فورد-جانسون چهار توابع بازگشتی به طوری محلی صدا زده می‌شوند، به این معنا که چهارضلعی‌ها در هر مرحله از توابع محلی بدست می‌آیند و تابع بازگشتی روی آرایه‌ای با اندازه ربع آرایه ورودی اتفاق می‌افتد، یعنی در این الگوریتم برای آرایه‌ای با طول n، توابع بازگشتی بر روی لیستی به اندازه{{عبارت چپ‌چین|<math> \lfloor \frac{n}{4} \rfloor</math>}} و سپس به روی آرایه‌ای با طول {{عبارت چپ‌چین|<math> \lfloor \frac{n}{4^2} \rfloor</math>}} و ... صورت می‌گیرد. برای این کار قسمت اول حافظه دیگیر می‌شود و قسمت دوم برای نگه‌داری اشاره‌گری به مکان اعضا نگه می‌دارد؛ بنابراین برای این الگوریتم ما از {{عبارت چپ‌چین|<math> \sum_{i=1}^{\lceil log_4 (n) \rceil -1}\lfloor \frac{n}{4^i} \rfloor</math>}} فضای حافظه استفاده می‌کند
این در حالی است که الگوریتم اصلی فورد-جانسون از {{عبارت چپ‌چین|<math> \sum_{i=1}^{\lceil log_2 (n) \rceil -1}\lfloor \frac{n}{2^i} \rfloor</math>}} فضای حافظه استفاده می‌کند:{{سخ}}
برای الگوریتم فورد-جانسون چهار
{{عبارت چپ‌چین|<math> \leftarrow</math>}}
{{سخ}}
{{عبارت چپ‌چین|<math> \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} </math>}}
{{سخ}}
برای الگوریتم اصلی فورد-جانسون
{{عبارت چپ‌چین|<math> \leftarrow</math>}}
{{سخ}}
{{عبارت چپ‌چین|<math> \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 </math>}}
* پس برای الگوریتم ما تنها ۳۳٪ فضای حافظه نسبت به الگوریتم اصلی فورد-جانسون مورد نیاز است.
* همچنین تعداد صدا زدن توابع بازگشتی الگوریتم پیشنهادی نسبت به فورد-جانسون اصلی براب با {{عبارت چپ‌چین|<math>\frac{\lfloor log_4 (n) \rfloor}{\lfloor log_2 (n) \rfloor} \leq \frac{1}{2}</math>}}

== جستارهای وابسته ==
* [[مرتب‌سازی حبابی]]
* [[مرتب‌سازی انتخابی]]
* [[مرتب‌سازی هرمی]]
* [[مرتب‌سازی ادغامی]]

== منابع ==
{{پانویس}}
* قدسی، محمد، [[داده ساختارها]] و مبانی الگوریتم‌ها، چاپ دوم، [[انتشارات فاطمی]]، ۱۳۸۹.
* [http://www.sciencedirect.com/science/article/pii/S0020019006002742 مقاله‌ای از مارتین پکزارسکی در سال ۲۰۰۶]
* [https://www.researchgate.net/publication/222571621_A_variant_of_the_Ford-Johnson_algorithm_that_is_more_space_efficient مقاله‌ای از مارسیو آیالا ریکون و برونو دآبرو در سال ۲۰۰۷]

[[رده:الگوریتم‌ها]]